Chapter 4
file. The PDD file contains the number of elements that belong to the IC and for each of them show main information like identifier, name, 2D-coordinates, and the list of interconnected elements. The PDD file is used as input for the new algorithm and its format is also employed for the output file that will contain for each element also the vertical coordinate that define the tier of belonging in the 3D placement. Is important to notice that the PDD representation manage the circuits like a graph in which the vertices are the elements and the edges are the interconnections. This graph-like definition is important because it push us to adopt solution feasible for hypergraphs and synergizes very well with the METIS package and its processes.
Figure 4.1: Section of PDD file
Before developing the algorithm, it is important to define, in addition to the objectives, the constraints to be respected during the execution of the processes.
The area of each tier should be smaller than the initial surface of the 2D IC because the density level must increase. Over more, the tiers area should be decided in relation to the number of elements to be placed in order to avoid wasting space.
Even if we try to minimize them, an excessive number of TSVs can lead to solutions that are not feasible for real production, so we should anyway check their quantity.
The position of a TSV should be chosen carefully because the elements belonging
to different levels, but connected by the same TSV, should have the same 2D-coordinates, thus being one above the other or at least as close as possible to this solution. The position of the pins is also subject to constraints; they can be placed only in the first or in the last layer of the 3D IC, in order to facilitate the connection with the main board. Moreover, pins should be allocated in a way that minimize the solution wirelength. To check if the algorithm is compliant with those constraints, during the execution, partial results are printed as output and graphical representation of the 3D IC are shown.
The Place and Route algorithm is composed by five steps that, starting from a 2D PDD file, are able to produce a final 3D PDD file containing for each element a 3D-coordinates that define the tier of belonging and the position on it. The objectives of the first three phases are the minimization of the number of TSVs, therefore the identification of the best level for each component of the IC.
The fourth step begins when each element has been assigned to a tier, now the main goal is finding the best 2D placement in each layer in order to minimize the wirelength. In this step is extremely important the placement of elements connected through TSVs with other tier’s components, for this reason different approaches were made to understand how the final solution can be affected. The fifth and last step focus on the placement of the pins which depend on the position of all the other components, for this reason it must be done as final operation. Besides the parameters necessary for execution, such as the input file and the number of tiers, the user is able to define other options that will change the algorithm’s behaviours. Is possible to set by a specific parameter if the tiers’ area should be computed starting by the total number of elements of the IC, or by the surface size of the initial 2D IC, that can be obtained by the minimum and maximum values of the 2D-coordinates. The user can also link an input file containing a list of elements’ names. All the components identify by these names belong to a specific tier and during the placement phase cannot be moved from it. This kind of feature can be very useful with IC characterized by peculiar architecture that require fixed position for some components. To give an example, for CNN inference[20] IC architecture was developed in which fixing the position of specific blocks can implementing low-latency and energy-efficient solution. To summarize
how the Place and Route algorithm works, its different steps are listed below with a brief description that will be expanded in further chapters.
1 - Modularization: Starting from the 2D PDD file a graph of the IC is composed.
The graph will be divided in sub-graphs (modules) that will become the base component of the algorithm, that will move them across the different tiers.
2 - BFS vertical placement: An initial tier is assigned to all the modules thanks to the exploration of the graph using Breadth First Search (BFS) algorithm.
3 - TSV optimization: By computing the cost of moving modules through all the distinct tiers is possible to find solution different to the initial ones that have a lower number of inter-tier interconnections.
4 - 2D placement: Once the components belonging to each tier have been defined, the modules are decomposed into the initial nodes which are placed in their layer following a policy of reducing the wirelength.
5 - Pins placement: The IC’s pins are placed on the first layer according to the distance with the others components.