Name
Title | ||
|---|---|---|
Improving the Efficiency of Scheduling and Placement in FPGA by Small-world Model Based Genetic Algorithm |
Abstract | ||
|---|---|---|
A genetic algorithm based on small-world model (GA-SW) is developed for solving the scheduling and placement problem in FPGA. In this problem, a set of tasks with their own start times, execution times and deadlines is to be scheduled into the FPGA with the objective to minimize the total delay of tasks. The small-world network model possesses locality character, i.e., tightly local connections and loosely remote connections, which can be directly used in the design of the initial population and mutation operator of GA since the optimal solutions for scheduling also has locality character, i.e., close to the deadline-based sequence. Meanwhile, a gliding window method is proposed along with the small-world model so as to better take advantage of the locality of solutions. Additionally, a converging crossover operator is developed to prevent invalid solutions caused by combinatorial coding. The time complexity of GA-SW is O(n2), where n is the number of tasks. Compared with traditional genetic algorithm, GA-SW can dramatically improve the efficiency of the algorithm and the quality of solutions. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/CIT.2010.58 | CIT |
Keywords | Field | DocType |
tightly local connections,placement problem,scheduling,small-world network model,placement,deadline-based sequence,locality character,loosely remote connections,encoding,converging crossover operator,combinatorial mathematics,small-world model,computational complexity,scheduling problem,small-world model based genetic algorithm,genetic algorithm,genetic algorithms,fpga,combinatorial coding,ga,small-world,traditional genetic algorithm,field programmable gate arrays,mutation operator,time complexity,small world network,tuning | Locality,Single-machine scheduling,Job shop scheduling,Crossover,Computer science,Scheduling (computing),Real-time computing,Time complexity,Genetic algorithm,Computational complexity theory,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4244-7547-6 | 0 | 0.34 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jie Cui | 1 | 5 | 3.57 |
| Xue Chen | 2 | 158 | 8.11 |
| Yong-mei Lei | 3 | 6 | 6.13 |
| Weimin Xu | 4 | 61 | 7.98 |