Research of synthesis algorithms for special-purpose multiprocessing systems with task-dependant architecture
Keywords in Hungarian
Többprocesszoros rendszerek, rendszer szintű szintézis, hardware/software együttes tervezés, magas szintű szintézis
Keywords in English
multiprocessing systems, system level synthesis, hardware/software codesign, high level synthesis
Discipline
Automation and Computer Science (Council of Physical Sciences)
50 %
Ortelius classification: Automation
Information Technology (Council of Physical Sciences)
50 %
Ortelius classification: Applied informatics
Panel
Informatics and Electrical Engineering
Department or equivalent
Department of Control Engineering and Information Technology (Budapest University of Technology and Economics)
Participants
Loványi, István Móczár, Géza Pilászy, György
Starting date
2008-04-01
Closing date
2012-10-31
Funding (in million HUF)
19.500
FTE (full time equivalent)
2.48
state
closed project
Summary in Hungarian
A korábbi OTKA támogatású kutatásaink során kifejlesztett algoritmusokat kiterjesztve lehetőség adódik feladatfüggő többprocesszoros célrendszerek szisztematikus szintézisére. Az ilyen rendszerek jelentősége egyre nagyobb, mert az áltanos célú többprocesszoros rendszerek alkotó elemei egyre komplexebbek (általános programozható eszközök, IP-k, jelfeldolgozó processzorok, stb.), Emiatt a nem feladatfüggő felépítés kommunikációs protokollja és általános célú operációs rendszere egyre bonyolultabb, így a teljes rendszer teljesítőképességének egyre nagyobb hányadát emésztik fel. A feladatfüggő felépítés szisztematikus szintézisére irányuló alapkutatatás jelentősége éppen az, hogy ezt a hátrányt el lehessen kerülni. Ha ugyanis olyan rendszer szintű szintézis algoritmusokat sikerül kidolgozni, amelyek a feladatfüggő felépítés ellenére szisztematikusak, akkor a feladatfüggésből adódó kötöttségek jelentősen csökkentik a kommunikációs protokoll és az operációs rendszer bonyolultságát. Az egyszerű feladatfüggő felépítés ezen túlmenően még azt is lehetővé teszi, hogy a korábbi OTKA támogatások keretében kifejlesztett PIPE tervező rendszer algoritmusait is felhasználva a teljes rendszer pipeline működését előre megadható újraindítási idővel a megengedett költség függvényében egyszerűen meg lehessen valósítani. A kutatás eredményeként létrejövő szintézis módszer a nemzetközi szakirodalomban várhatóan érdeklődést vált ki. A részeredményeket konferenciákon, teljes módszert rangos folyóiratban, vagy könyvfejezetként tervezzük publikálni. Az eredmények birtokában a korábbi külföldi partnereinkkel együttműködve kezdeményezzük a közös nemzetközi pályázatokon való részvételt.
Summary
Based on our earlier research supported by OTKA and on the extension of the algorithms developed earlier, the systematic synthesis of task-dependant multiprocessing special-purpose systems can be targeted. The importance of such systems is growing, since the components of the general-purpose multiprocessing systems become more and more complex (programmable processors, IP-s, DSP-s, etc.). Therefore the communication protocol and the operating system of a not-task-dependant architecture become very sophisticated and consume a great quantity from the system capacity. The basic research aiming the systematic synthesis of the task-dependant systems has just the main goal to avoid these drawbacks. Namely, if such system level synthesis algorithms were to be found which are systematic despite the task-dependant architecture, then the constraints caused by the task-dependence would simplify the communication protocol and the operating system on a great extent. Besides that, the simple task –dependant architecture enables the easy pipeline implementation of the whole system for a restarting period (throughput) given in advance considering the cost function also by applying the algorithms of our CAD tool PIPE developed in the frame of earlier OTKA supports. The synthesis method expected as a result of the research may have interest in the international literature. We are planning to publish the results separately on conferences, and the whole method in a relevant international journal or as a book chapter. After having achieved the results, we shall initiate to take part in international project applications in cooperation with our earlier foreign partners.
Final report
Results in Hungarian
Új módszert és egy keretrendszert fejlesztettünk ki olyan speciális többprocesszoros struktúra tervezésére, amely lehetővé teszi a pipeline működtetést akkor is, ha a feladat-leírásban nincs hatékonyan kihasználható párhuzamosság. A szintézis egy magas szintű nyelven (C, Java, stb.) adott feladatleírásból indul ki. Ezután dekompozíciós algoritmus megfelelő szegmenseket képez a program alapján. A szegmensek kívánt száma, a szegmenseket megvalósító processzorok főbb tulajdonságai és a becsült kommunikációs időigények megadhatók bemeneti paraméterekként. Kedvező pipeline felépítés céljából a pipeline adatfolyamok magas szintű szintézisének (HLS) módszertanát alkalmaztuk. Ezek az eszközök az ütemezés és az allokáció révén kísérlik meg az optimalizálást a szegmensekből képzett adatfolyam gráfon. Ezért a kiadódó többprocesszoros felépítés nem egy uniformizált processzor-rács, hanem a megoldandó feladatra formált struktúra, így feladatfüggőnek nevezhető. A módszer modularitása lehetővé teszi a dekompozíciós algoritmusnak és a HLS eszköznek a cseréjét, módosítását az alkalmazási igényektől függően. A módszer kiértékelése céljából olyan HLS eszközt alkalmaztunk, amely a kívánt pipeline újraindítási periódust bemeneti adatként tudja kezelni, és processzorok között egy optimalizált időosztásos, arbitráció-mentes sínrendszert hoz létre. Ebben a struktúrában a kommunikáció szervezéséhez nincs szükség külön szoftver támogatásra, ha a processzorok képesek közvetlen adatforgalomra.
Results in English
A new method and a framework tool has been developed for designing a special multiprocessing structure for making the pipeline function possible as a special parallel processing, even if there is no efficiently exploitable parallelism in the task description. The synthesis starts from a task description written in a high level language (C, Java, etc). A decomposing algorithm generates proper segments of this program. The desired number of the segments, the main properties of the processor set implementing the segments and the estimated communication time-demand can be given as input parameters. For constructing a pipeline structure, the high-level synthesis (HLS) methodology of pipelined datapaths is applied. These tools attempt to optimize by scheduling and allocating the dataflow graph generated from the segments Thus, the resulted structure is not a uniform processor grid, but it is shaped depending on the task, i.e. it can be called task-dependent. The modularity of the method permits the decomposition algorithm and the HLS tool to be replaced by other ones depending on the requirements of the application. For evaluating the method, a specific HLS tool is applied, which can accept the desired pipeline restart time as input parameter, and generates an optimized time shared simple arbitration-free bus system between the processing units. Therefore, there is no need for extra efforts to organize the communication, if the processing units can transfer data directly.
P. Arató, I. Loványi, G.Patai, G. Suba, M. Timotity, T. Torba: Compiling High Level Flow Languages into Hardware (Survey), Morgan Stanley Magyarország Kft., BME Irányítástechnika és Informatika Tanszék, 2010
P. Arató, B. Csák: Pipeline mode in C-based direct hardware implementation, Periodica Polytechnica (El. Eng.) 52 3-4 2008, 2011
P. Arató, D. Drexler, G. Kocza, G. Suba: Synthesis of a Task-dependent Pipelined Multiprocessing Structure, ACM Transactions on Design Automation of Electronic Systems (közlésre elküldve), 2013
György Pilászy, György Rácz, Péter Arató: Communication Time Estimation in High Level Synthesis, Periodica Polytechnica (El. Eng.), (közlésre elküldve), 2013
Gy. Rácz, G. Móczár, Gy. Pilászy: Efficient microcontroller based methods for single phase induction motorr control, Proceedings of 2nd ISW on DCS, Miskolc-Lillafüred, 2011
P. Arató: High-Level Synthesis of a Task-Oriented Multiprocessing Structure, IRUN Workshop on the Theory and Practice of Kiloprocessor Architectures, Pázmány Péter Catholic University, 2012
P. Arató, G. Kocza, I. Loványi: Acceleration of KLT tracking using special-purpose hardware design, Proceedings of the 1st International Congress On Pervasive Computing, New Delhi, 12-14 December 2008, p34, 2008
