Speeding innovation for industry
Smart digital systems
The IEEE International Parallel and Distributed Processing Symposium 2018 coincided with the 25th anniversary of the Reconfigurable Architectures Workshop (RAW). To mark the milestone, a floor planning competition was held, where competitors were asked to develop algorithms to predict the positions of various elements of FPGA-type programmable components. List won first prize in the competition.
The challenge was to find the solution capable of reducing the surface area occupied by functional blocks to the bare minimum while reducing the total connection length as much as possible. List's algorithm used simulated annealing, a method for resolving optimization problems. The method keeps the program from getting "stuck" on a localized optimal configuration. However, to ensure that the best possible solution was generated, List developed a "multistart" approach that restarts the calculations with several different initial solutions to vary the results and find the optimal solution or get as close to the optimal solution as possible.
The program, which verifies all of the constraints of the problem (and others), made List the only competitor to obtain a solution for all 30 problems assigned for the competition. The win highlights List's know-how in operational research and combinatorial optimization applied to electronic circuit design automation.
CEA is a French government-funded technological research organisation in four main areas: low-carbon energies, defense and security, information technologies and health technologies. A prominent player in the European Research Area, it is involved in setting up collaborative projects with many partners around the world.