**** Master Project or Semester Project ****
Contact: Dr. Mathias Soeken, Post-doctoral researcher, EPFL-IC-ISIM-LSI
Background of the project:
The logic representations which are used by logic synthesis algorithms are typically simple graph structures, such as And-inverter graphs (AIGs) or Majority-inverter graphs (MIGs, [1]). The vertices in the graph either represent a logic operation (AND or majority-of-three), a primary input, or a constant value. Edges may be complemented or not. These data structures are sufficient to represent any Boolean function and particularly due to their simplicity they are a convenient basis for powerful algorithms. Since the considered Boolean function often represent large circuits or designs, the graphs quickly become very large. This makes the implementation of memory and run-time efficient algorithms very difficult. For this purpose, most of the algorithms are developed in machine oriented programming languages such as C and C++.
Overview of the project:
The project targets the implementation of logic synthesis algorithms that are inherently parallel using cluster computing frameworks, in particular Apache Spark. Since the logic representations are graph data structures, they can be stored and manipulated using Apache Spark’s GraphX. Some of these ideas have been mentioned and presented in [2,3].
Tasks in the project are: i) developing efficient data structures for AIGs and MIGs on top of GraphX, ii) developing efficient atomic manipulation routines for the data structures, and iii) developing parallel versions of state-of-the-art logic synthesis algorithms on top of the Apache Spark infrastructure. Suitable algorithms are event-driven synthesis, random simulation, pattern matching, or cut enumeration.
Eligibility requirements:
- Good background in data structures
- Proficiency in Scala, or alternatively Java
- Knowledge on Apache Spark and/or logic synthesis is a plus
References:
[1] L.G. Amarù, P.E. Gaillardon, G. De Micheli: MajorityInverter Graph: A Novel DataStructure and Algorithms for Efficient Logic Optimization. DAC 2014: 194:1194:6.
[2] L. Stok: Developing Parallel EDA Tools [The Last Byte]. IEEE Design & Test 30(1): 6566 (2013).
[3] L. Stok: The Next 25 Years in EDA: A Cloudy Future? IEEE Design & Test 31(2): 4046 (2014).