Researches On The Algorithms Of Searching Empty Resources Based On Two-dimensional Dynamic Reconfigurable Model

Reconfigurable computing is a new computing way between software and appli-cation specific integrated circuit．It takes on the flexibility of software and high ef-ficiency of hardware．In order to take full advantage of reconfigurable hardware inhigh-performance and flexibility as well as simplify the management of reconfigur-able logic device, studies have proposed the thinking of taking functional hardwaremodule as hardware task and let the operation system to unify the task of software andhardware. This refers to finding the suitable empty space for hardware task. Therefore,the search strategy of empty resources for reconfigurable hardware is one of the re-search points of reconfigurable computing field.The main work of this thesis is to study the current search strategies of emptyspace for reconfigurable system and it proposed three algorithms of searching emptyresources based on maximal empty rectangle. SSLA1(Strengthened Scan Line Algo-rithm1)、SSLA2(Strengthened Scan Line Algorithm2)、SLA_VP(Scan Line Algo-rithm, Valley Point). The basic idea of these algorithms is to search for valid searchwidth while searching for maximal empty rectangles. Among them, SSLA1andSSLA2adopt the idea of searching orderly and valid search width. It ensures the re-sult that every time searching will be maximal empty rectangles. But the sequence ofthese two algorithms is different. SSLA1follows ascending order while SSLA2follows descending order. Thru establishing one-dimension array, these two algo-rithms avoid the problem of repeated search by considering the unit to be zero for thesame orderly and valid search width when doing the search. Compared to ESLA whichadopts two-dimension assisting array, these two algorithms effectively reduce the costof assisting storage space. Thru further study, we found that the valley point betweenthese two maximum key elements has the following characteristic. If the unit data ofvalley point is not zero the maximal empty rectangle, which covers maximum keyelements, exists. Thru the way of keeping the informs of valley point, SLA-VP judgethe two maximum key elements if they are adjacent and taking advantage of thecharacteristic of valley point to confirm the minimum efficient searching width, thusavoiding the problem of repeated searching. The cost of assisting storage space re-duces compared to the previous two algorithms.Finally, the experiments examined the performance of the proposed algorithms. And results show the average running time cost of these three new algorithms are lessthan ESLA. And among these three algorithms, the average running time cost forSSLA1and SSLA2are less than SLA-VP. The average running time cost for SSLA1ismore than SSLA2When the load factor is less than50%. On the contrary, SSLA1isbetter than SSLA2.