FPGA Task Arrangement with Genetic Algorithms

Über dieses Buch

Art: Diplomarbeit
Autor: Bernd Scheuermann
Abgabedatum: Juli 1999
Umfang: 144 Seiten
Dateigröße: 1,4 MB
Note: 1,0
Institution / Hochschule: Universität Fridericiana Karlsruhe (TH) Deutschland
ISBN (eBook): 978-3-8324-2299-8
ISBN (Paperback) :
978-3-8324-2299-8 P
ISBN (CD) :978-3-8324-2299-8 CD
Sprache: Englisch
Prämierung:
Arbeit zitieren: Scheuermann, Bernd Juli 1999: FPGA Task Arrangement with Genetic Algorithms, Hamburg: Diplomica Verlag
Schlagworte: reconfigurable Computing, FPGA, verkonfigurierbares Rechnen, Field Programable Logic, genetischer Algorithmus

In den Warenkorb
38,00 €

Erhältlich als:
PDF-eBook Download: 38,00 € PDF-eBook auf CD: 38,00 € Ausdruck eBook: 38,00 €

Diplomarbeit von Bernd Scheuermann

Abstract:

Two evolutionary approaches of allocating tasks onto a Field-Programmable Gate Array (FPGA) are presented.

Offline task arrangement: whenever a set of tasks has to be arranged onto an FPGA in practice, one is interested in arranging a maximum number of tasks which efficiently utilize the FPGA area. A genetic algorithm is proposed searching for an arrangement of tasks offline, i.e. before the tasks are physically placed onto the FPGA.

Online task arrangement: FPGAs that allow partial reconfiguration at run-time can be shared among multiple independent tasks. When the sequence of tasks to be performed is unpredictable the FPGA controller needs to make allocation decisions online. Since online allocation suffers from fragmentation, tasks can end up waiting despite there being sufficient, albeit non-contiguous resources available to service them. The time to complete tasks is consequently longer and the utilization of the FPGA is lower than it could be. A genetic algorithm is proposed rearranging a subset of the tasks executing on the FPGA when doing so allows the next pending task to be processed sooner. In comparison with other heuristic approaches a genetic algorithm is described and evaluated which overcomes the NP-hard problems of identifying feasible rearrangements and scheduling the rearrangements when moving tasks are reloaded from off-chip.

Table of Contents:

1.	Introduction	7
2.	Field Programmable Gate Arrays	9
2.1	Architecture of FPGAs	9
2.2	Dynamically Reconfigurable FPGAs	10
2.3	Comparison with Related Devices	11
2.4	Creation of an FPGA Model	11
3.	FPGA Task Arrangement Problem	18
3.1	Static Task Arrangement Problem	18
3.1.1	Static Task Management	18
3.1.2	Problem Formulation	20
3.2	Dynamic Task Arrangement Problem	21
3.2.1	Dynamic Task Management	21
3.2.2	Search for an Admissible Task Rearrangement	22
3.2.3	Rearrangement Scheduling	24
3.2.4	Buffer Restriction	27
3.2.5	Problem Formulation	30
4.	Arrangement Concepts	31
4.1	Shape Functions	31
4.2	Slicing Trees	35
5.	Genetic Algorithms	41
5.1	Introduction	41
5.2	The Functioning of Genetic Algorithms	43
5.3	Main Components of Genetic Algorithms	45
5.3.1	Representation	45
5.3.2	Initialization	46
5.3.3	Evaluation	47
5.3.4	Stopping Condition	47
5.3.5	Reproduction	47
5.3.6	Selection	48
5.3.7	Genetic Operators	49
6.	Static Task Arrangement	51
6.1	Representation	51
6.2	Initialization	52
6.2.1	Random Pairing	53
6.2.2	Traversal of Flexible Slicing Trees	53
6.3	Evaluation	56
6.4	Genetic Operators	56
6.4.1	Mutation	57
6.4.2	Crossover	61
7.	Dynamic Task Arrangement	65
7.1	Background GA	65
7.1.1	Initialization	65
7.1.2	Evaluation	66
7.1.3	Events	67
7.2	Task Remove Event	68
7.3	New Task Event	68
7.3.1	Search for Rearrangement	70
7.3.2	Scheduling GA	73
7.3.3	Population Update	76
8.	Experimental Results	78
8.1	Performance of Static Task Arrangement	78
8.1.1	Test Data Generation	79
8.1.2	Overview of Experiments	81
8.1.3	Performance of Initialization	81
8.1.4	Performance of Mutation	85
8.1.5	Performance of Crossover	89
8.1.6	Task Parameter Effect	95
8.2	Performance of Dynamic Task Arrangement	97
8.2.1	Other Approaches by Diessel	98
8.2.2	Simulation-Specific Modifications	99
8.2.3	Test Data Generation	101
8.2.4	Overview of Experiments	104
8.2.5	Relation between System Load and Allocation Performance	105
8.2.6	Relation between Configuration Delay and
Allocation Performance	110
9.	Conclusion	115
A.	Program Documentation	117
A.1	Static Task Arrangement	117
A.1.1	The File Submenu	118
A.1.2	The Control Submenu	119
A.1.3	The Settings Submenu	119
A.1.4	The Window Submenu	124
A.1.5	The Tool Bar	126
A.2	Dynamic Task Arrangement	127
A.2.1	The File Submenu	128
A.2.2	The Control Submenu	128
A.2.3	The Settings Submenu	129
A.2.4	The Window Submenu	132
A.2.5	The Tool Bar	135