10.14489/vkit.2018.09.pp.003-010

DOI: 10.14489/vkit.2018.09.pp.003-010

Алексеев К. Н., Сорокин Д. А., Левин И. И.
СТРУКТУРНО-ПРОЦЕДУРНАЯ РЕАЛИЗАЦИЯ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ КОДИРОВАНИЯ ХАФФМАНА В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ
(c. 3-10)

Аннотация. Рассматриваются принципы синтеза параллельно-конвейерных программ для решения задач реального времени на реконфигурируемых вычислительных системах (РВС). Традиционные методы синтеза параллельно-конвейерных программ для РВС гарантируют решение задачи на определенной конфигурации системы, однако используемый ресурс РВС в случае решения задач реального времени может быть избыточен. При реализации на РВС задач реального времени часто требуется выполнение расчета минимальной конфигурации системы с учетом заданных параметров ее производительности, точности решения задачи, а также габаритов изделия, энергопотребления и надежности. Предложен новый подход к синтезу параллельно-конвейерных программ для РВС, заключающийся в приведении реальной производительности синтезируемой вычислительной структуры задачи к заранее заданной. Данный подход предполагает особое преобразование информационного графа задачи на основе анализа аппаратных затрат на реализацию синтезируемого решения. Описан новый метод редукции производительности, который в отличие от существующих методов выполняется единовременно и приводит производительность задачи к изначально заданному уровню. Используемые в статье инструменты позволяют находить минимальный аппаратный ресурс, необходимый для реализации задачи. Новый метод создания параллельно-конвейерных программ для РВС проиллюстрирован на примере задачи кодирования потока данных методом Хаффмана. Предложенный подход позволил определить наиболее подходящую конфигурацию вычислительной системы для конкретных условий поставленной задачи. Данный подход предполагается применять при необходимости выбора оптимальной конфигурации РВС для решения задач, характеризующихся либо фиксированной производительностью вычислений, либо ограниченной скоростью обработки данных.

Ключевые слова: реконфигурируемые вычислительные системы; синтез параллельно-конвейерных программ; задачи реального времени; кодирование Хаффмана.

Alekseev K. N., Sorokin D. A., Levin I. I.
STRUCTURAL-PROCEDURAL IMPLEMENTATION THE HUFFMAN CODING ON RECONFIGURABLE COMPUTER SYSTEMS IN REAL TIME
(pp. 3-10)

Abstract. The paper covers principles of parallel-pipeline program synthesis for solving realtime problems on reconfigurable computer systems (RCS). Using traditional methods of parallel-pipeline program synthesis for RCS are guaranteed the problem solution on a certain system configuration. However, the resource, used by RCS in realtime problems, can be excessive. The calculation of minimum system configuration taking into account the given parameters of system performance, the accuracy of problem solution, as well as the product dimensions, the energy consumption and reliability is often required in implementing realtime problems on RCS. A new approach to the synthesis of parallel-pipeline programs for RCS was proposed in the paper. It consist in bringing the real performance of a synthesized computational structure of the problem to a predetermined. This approach involves a special transformation of the information task graph based on the analysis of hardware costs for implementation the synthesized solution. A new method of performance reduction was described, which is executed simultaneously, compared to the existing methods, and resulted the performance of problem to the initial given level. Due to the means, described in the paper, we can determine the minimum hardware resource, required for the problem. The new method of designing the parallel-pipeline programs for RCS was illustrated on the example of data flow coding problem by the Huffman method. Due to the proposed approach, we determined the most appropriate configuration of the computer system for specific conditions of the problem. The described approach can be used for chosen the optimal RCS configuration for solving problem, characterized by either fixed performance of calculations or limited speed of data processing.

Keywords: Reconfigurable computer systems; Synthesis of parallel-pipeline programs; Realtime problems; Huffman codding.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

К. Н. Алексеев, Д. А. Сорокин (Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров, Таганрог, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
И. И. Левин (Институт компьютерных технологий и информационной безопасности Южного федерального университета, Таганрог, Россия)

Eng

K. N. Alekseev, D. A. Sorokin (Supercomputers and Neurocomputers Research Center, Taganrog, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
I. I. Levin (Institute of Computer Technologies and Information Security of the Southern Federal University, Taganrog, Russia)

+ - Библиографический список (References) Click to collapse

Рус

1. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев и др.; под общ. ред. И. А. Каляева. Изд. 2-е, перераб. и доп. Ростов н/Д: Изд-во ЮНЦ РАН, 2008. 397 с.
2. Каляев А. В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984. 240 с.
3. Каляев А. В., Левин И. И. Многопроцессорные системы с перестраиваемой архитектурой: концепции развития и применения // Наука – производству. 1999. № 11. С. 11 – 19.
4. Каляев А. В., Левин И. И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. 380 с.
5. Левин И. И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений: дис. … д-ра техн. наук: 05.13.11, 05.13.15. Таганрог, 2004. 363 с.
6. Lelewer D. A., Hirschberg D. S. Data Compression // ACM Computing Surveys. 1987. V. 19, No 3. P. 261 – 297. doi: 10.1145/45072.45074
7. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин и др. М.: ДИАЛОГ-МИФИ, 2002. 384 с.
8. Deutsch L. P. RFC 1951–DEFLATE Compressed Data Format Specification Version 1.3, 1996. [Электронный ресурс]. Режим доступа: http://www. faqs.org/ rfcs/rfc1951.htm (дата обращения: 10.06.2018)
9. Сорокин Д. А. Методы решения задач с переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах: дис. … канд. техн. наук: 05.13.11. Ростов н/Д, 2012. 165 с.
10. Дордопуло А. И., Сорокин Д. А. Методика сокращения аппаратных затрат в сложных системах при решении задач с существенно-переменной интенсивностью потоков данных // Изв. ЮФУ. Технические науки. 2012. № 4(129). С. 194 – 199.
11. Программирование вычислительных систем гибридного типа на основе метода редукции производительности / А. И. Дордопуло и др. // Параллельные вычислительные технологии (ПаВТ’2016): сб. тр. Междунар. науч. конф., г. Архангельск, 28 марта – 1 апр. 2016 г. / отв. ред.: Л. Б. Соколинский, И.И. Стародубов. Челябинск, 2016. С. 131 – 140.
12. All Programmable 7 Series Product Selection Guide. 2018. 12 p. [Электронный ресурс]. URL: https://www.xilinx.com/support/documentation/selection-guides/7-series-product-selection-guide.pdf#K7 (дата обращения: 10.06.2018).
13. Кнут Д. Э. Искусство программирования: в 7 т. Т. 3. Сортировка и поиск: пер. с англ. 2-е изд. М.: Вильямс, 2007. 832 с.
14. Дябилкин Д. А. Сортирующие сети: методическое пособ. Казань: Изд-во Казан. ун-та, 2015. 13 с.
15. Левин И. И., Пономарев И. М. Структурная реализация сортировки массивов на основе сети Батчера // Искусственный интеллект. 2004. № 3. С. 198 – 202.
16. Гузик В. Ф., Каляев И. А., Левин И. И. Реконфигурируемые вычислительные системы: учебник / под общ. ред. И. А. Каляева. Ростов н/Д: Изд-во ЮФУ, 2016. 472 с.

Eng

1. Kalyaev I. A. (Ed.) et al. (2008). Reconfigurable multicore computing structures. 2nd Ed. (revised and complemented). Rostov-on-Don: Izdatel'stvo YUNTS RAN. [in Russian language]
2. Kalyaev A. V. (1984). Multiprocessor computing systems with programmable architecture. Moscow: Radio i svyaz'. [in Russian language]
3. Kalyaev A. V., Levin I. I. (1999). Multiprocessor systems with a reconfigurable architecture: concepts of development and application. Nauka – proizvodstvu, (11), pp. 11-19. [in Russian language]
4. Kalyaev A. V., Levin I. I. (2003). Modularscalable multiprocessor systems with structural-procedural organization of calculations. Moscow: Izdatel'stvo «Yanus-K». [in Russian language]
5. Levin I. I. (2004). Methods and hardware-software of parallel structural-procedural calculations. Taganrogskiy radiotekhnicheskiy institut. Taganrog. [in Russian language]
6. Lelewer D. A., Hirschberg D. S. (1987). Data Compression. ACM Computing Surveys, 3, pp. 261-297. doi: 10.1145/45072.45074
7. Vatolin D. et al. (2002). Methods of data compression. The device archivers, image compression and video. Moscow: Izdatel'stvo DIALOG-MIFI. [in Russian language]
8. Deutsch P. (1996). RFC 1951–DEFLATE Compressed Data Format Specification Version 1.3. Available at: http://www.faqs.org/ rfcs/rfc1951.htm (Accessed: 10.06.2018)
9. Sorokin D. A. (2012). Methods for solving problems with variable intensity of data streams on reconfigurable computer systems. Yuzhnyy Federal'nyy institut. Rostov-on-Don. [in Russian language]
10. Dordopulo A. I., Sorokin D. A. (2012). A technique for reducing hardware costs in complex systems for solving problems with an essentially variable intensity of data flows. Izvestiya YuFU. Tekhnicheskie nauki, 129(4), pp. 194-199. [in Russian language]
11. Dordopulo A. I. et al. (2016). Programming of Hybrid-Type Computing Systems Based on the Productivity Reduction Method. Parallel Computing Technologies 2013 (PaVT’2016): proceedings of the International scientific conference. Chelyabinsk: Izdatel'skiy tsentr YuUrGU, pp. 131-140. [in Russian language]
12. 7 Series Product Tables and Product Selection Guide. (2018). Available at:https://www.xilinx. com/support/documentation/selection-guides/7-series-product-selection-guide.pdf#K7 (Accessed: 10.06.2018)
13. Knut D. (2007). The art of programming. Sorting and searching. Vol. 3. 2nd Ed. (pp. 192-201). Moscow: Vil'yams. [in Russian language]
14. Dabilkin D. A. (2015). Sorting networks: a methodical guide. Kazan: Izdatel'stvo Kazanskogo universiteta. [in Russian language]
15. Levin I. I., Ponomarev I. M. (2004). Structured implementation of array sorting based on the network Butcher. Iskusstvennyy intellekt, (3), pp. 198-202. [in Russian language]
16. Guzik V. F., Kalyaev I. A. (Ed.), Levin I. I. (2016). Reconfigurable Computing Systems. Rostov-on-Don: Izdatel'stvo YuFU. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2018.09.pp.003-010

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2018.09.pp.003-010

and fill out the form