"Eesti Teadusfondi uurimistoetus" projekt ETF9251
ETF9251 "Rekonfigureeritav protsessor kombinatoorsete ülesannete lahendmiseks puulaadsete andmestruktuuride baasil (1.01.2012−31.12.2015)", Aleksander Sudnitsõn, Tallinna Tehnikaülikool, Infotehnoloogia teaduskond.
ETF9251
Rekonfigureeritav protsessor kombinatoorsete ülesannete lahendmiseks puulaadsete andmestruktuuride baasil
Reconfigurable Processor for Problems of Combinatorial Computations over Tree-like Data Structures
1.01.2012
31.12.2015
Teadus- ja arendusprojekt
Eesti Teadusfondi uurimistoetus
ETIS klassifikaatorAlamvaldkondCERCS klassifikaatorFrascati Manual’i klassifikaatorProtsent
4. Loodusteadused ja tehnika4.8. Elektrotehnika ja elektroonikaT170 Elektroonika 2.2. Elektroenergeetika, elektroonika (elektroenergeetika, elektroonika, sidetehnika, arvutitehnika ja teised seotud teadused)50,0
4. Loodusteadused ja tehnika4.6. ArvutiteadusedP170 Arvutiteadus, arvutusmeetodid, süsteemid, juhtimine (automaatjuhtimisteooria)1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)50,0
PerioodSumma
01.01.2012−31.12.20127 080,00 EUR
01.01.2013−31.12.20137 080,00 EUR
01.01.2014−31.12.20147 080,00 EUR
01.01.2015−31.12.20157 080,00 EUR
28 320,00 EUR

Eksisteerib väga palju tehnilis-praktilisi rakendusi, mis nõuavad keerukate kombinatoorsete ülesannete lahendamist. Suurem osa sellistest ülesannetest on NP-täielikud ning tänu sellele väga aja- ning ressursinõudlikud. Rekonfigureeritav protsessor kombinatoorsete ülesannete lahendamiseks, mis projekteeritakse põhjalike teoreetiliste uuringute baasil, võimaldab nimetatud ülesannete lahendamiseks vajalike ressursside olulist vähendamist rekonfigureeritavatele digitaalsüsteemidele orienteeritud optimeerimistehnikate abil. Idee seisneb selles, et kombinatoorset lähenemist rakendatakse optimaalse hulga andmete jaoks ning kombineeritakse seda lähenemist viitadel baseeruvate andmestruktuuridega nagu näiteks puulaadsed struktuurid. Puulaadsete struktuuride oluliseks eeliseks teiste tuntud andmemudelite ees on võimalus kiiresti kohaneda võimalike muudatustega, mis on äärmiselt oluline andmevoo töötlemise realiseerimisel. Hiljuti olid Aveiro Ülikooli ning käesoleva projekti taotlejate koostöö tulemusena välja pakutud uudsed meetodid kombinatoorseteks arvutusteks puulaadsete struktuuride baasil. Pakutud lähemise eelised olid seejuures demonstreeritud kasutades tarkvaralist simuleerimist, FPGA-põhist prototüüpimist ning arvutuslikke eksperimente. Keerukad kombinatoorsed arvutused realiseeritakse rakendus-spetsiifilise protsessori arhitektuuri abil, mis võimaldab baasoperatsioonide maatriksipõhise alamhulga täitmist. Protsessor ise luuakse reaalselt olemasolevate FPGA-de baasil. Parima realisatsiooni saamiseks võetakse seejuures arvesse erinevaid spetsiifilisi aspekte nagu ülesande optimaalne tükeldamine üldotstarbelise tarkvara ning lahendus-spetsiifilise rekonfigureeritava riistvara vahel, meetodid tarkvara ning riistvara vaheliseks suhtlemiseks ning andmevahetuseks, rakendatavad rekursiivsed või iteratiivsede arvutusmeetodid, eriotstarbeliste ahelate kasutamine maatriks-spetsiifiliste arvutuste läbiviimiseks, madala enegriatarbega disain. Kõiki eelnimetatud tegureid on planeeritud projekti käigus põhjalikult uurida ning tulemuste põhjal formuleerida teoreerilistel ja eksperimentaalsetel tõestustel baseeruvad nõuded kirjeldatud protsessorile. Uuringud viiakse läbi tihedas koostöös DETI/IEETA ning Aveiro Ülokooliga. Projekti tulemusi on planeeritud kasutada Elektroonika ning info- ja kommunikatsioonitehnoloogia kompententsukeskuses ELIKO ning Integreeritud elektroonikasüsteemide ja biomeditsiinitehnika tippkeskuses CEBE.
There are many practical applications that require solution of combinatorial problems. Majority of these problems are NP-complete and as a result they are very time and resource consuming. Reconfigurable processor for problems of combinatorial computations, that is going to be designed on the basis of deep theoretical investigations, will permit to reduce the required resources with the aid of optimization technique for reconfigurable digital systems. The idea is to apply combinatorial technique for a reasonable number of data and to combine this technique with pointer-based data structures, such as tree-like structures. An important advantage of tree-like structures compared to other known models is an opportunity of rapid adaptation to potential modifications that is very important for implementation of data stream processing. Recently, novel methods for combinatorial computations over tree-like structures and their implementation in hardware have been proposed as a team-work of researchers from Aveiro University and the applicant of this project. The advantages of the proposed techniques were demonstrated through simulation in software, prototyping in FPGA, and experiments. Complex combinatorial computations will be implemented in application-specific architecture of the processor which can execute a matrix-oriented subset of primary operations. The processor will be constructed on the basis of commercially available FPGAs. Note that the best result for the considered computations can be achieved if many different elements are taken into account, such as optimal partitioning the problem between general-purpose software and application specific reconfigurable hardware, methods of interactions and data exchange between software and reconfigurable hardware, computational technique, such as either recursive or iterative, using dedicated circuits for matrix specific computations, low-power design. All this factors are going to be carefully investigated and the relevant proposals based on theoretical and experimental proofs will be formulated. Studies will be conducted in close collaboration with the DETI/IEETA, University of Aveiro (Portugal). Potentially results would be used by organizations involved to Competence Centre in Electronics-, Info- and Communication Technologies ELIKO and Centre for Integrated Electronic Systems and Biomedical Engineering - CEBE.
Projeki põhieesmärgiks oli algoritmide välja töötamine nende efektiivseks riistvaraliseks realiseerimiseks rekonfigureeritavatel süsteemidel. Peamised teadustulemused on järgmised: • Uuriti uus hierarhilise lõpliku automaadi (HFSM) mudel, mis toetab modulaarsust ja rekursiivsust. • Pakuti välja uudsed meetodid kombinatoorseteks arvutusteks, mis lubavad esitada ja töödelda puulaadseid struktuure riistvaras. • On välja töötatud kombinatoorsete ülesannete riistvaralised lahendajad FPGA programmeeritavatel loogikaseadmetel. Eesmärgiks on diskreetsete maatriksite kaudu esitatud kombinatoorsete otsingualgoritmide efektiivne paraleelne teostus. • On välja töötatud lühima katte ülesanne (matrix/set covering problem) riistvaraline lahendaja FPGA programmeeritavatel loogikaseadmetel. • Uued andmete sorteerimisalgoritmide realisatsioonid rekonfigureeritavatel FPGA põhistel arhitektuuridel. • On välja töötatud meetod kõrgtootlike arvutisüsteemide projekteerimiseks, kus andmevoogude paralleelne kiirtöötlus programmeeritavas loogikaskeemis on kombineeritud probleemispetsiifilise tarkvaraga RISC protsessorites. • On välja töötatud riistvaraline lahendaja FPGA programmeeritavatel loogikaseadmetel. Riistvaraline lahendaja on teostatud töötluskeskkonnas Zynq xc7z020. • Pakutud lähemise eelised olid seejuures demonstreeritud kasutades tarkvaralist simuleerimist, FPGA-põhist prototüüpimist ning arvutuslikke eksperimente. Uuringud oli tehtud tihedas koostöös Aveiro Ülokooliga (Portugal). Tulemused on integreeritud tippkeskuses CEBE (Centre for Integrated Electronic Systems and Biomedical Engineering). Käsitletavast uurimisteemast on avaldati 5 ajakirjaartiklit (ETIS kategooria 1.1), 2 ajakirjaartiklit (ETIS kategooria 1.2), 15 artiklit mainekatel rahvusvahelistel konverentsidel (ETIS kategooria 3.1), 1 monograafia (ETIS 2.2), 1 raamat (ETIS kategooria 2.4). Tulemused on esitatud 14 rahvusvahelisel teaduskonverentsil.