A Heuristic For Optimizing The Physical Layout And Network Topology Of Integrated 3D Multi-chip Systems Under Temperature Constraints

Abstract

Many-core architectures provide large amounts of computational power and should thus be well-suited to running parallel applications. In this context, Integrated 3D multi-chip systems comprise multiple multi-core processor chips in a single tightly-coupled system. Heat dissipation is a major issue when designing integrated 3D multi-chip systems. It may not be possible to operate chips at their maximum frequency due to their being in close proximity to each other, which impedes heat dissipation. The physical layout of the chips is thus an important design consideration, also because it impacts the inter-chip network topology since a sparser physical layout can imply a less tightly-connected topology. Overall, there is a complex trade-off between between temperature, physical layout, chip operating frequencies, and inter-chip network topologies. The ThruChip Interface (TCI) makes wireless communications between processor chips possible via inductive coupling, and thus can be used to construct inter-chip networks. Inductive coupling offers economical advantages (e.g., ability to produce/test individual chips before their are integrated in a multi-chip system), while also providing sufficient bandwidth between communicating chips with low power consumption. Furthermore, this technology makes it possible to construct integrated 3D multi-chip systems using a wide range of physical layout options: it is only necessary for two chips to overlap for them to be connected, the network bandwidth being proportional to the overlap area. In this thesis we assume the use of TCI and focus on building integrated 3D multi-chip systems using physical chip layouts that afford good heat dissipation, high chip operating frequencies, and good inter-chip network topologies. This amounts to solving a constrained multi-objective optimization problem. Previously proposed physical layouts for integrated 3D multi-chip systems include the “stack,” which consist of multiple chips stacked vertically above one another, and the “checkerboard,” which consists of chips connected via partial overlaps at each of the four corners so as to resemble a checkerboard when viewed from above. These baseline layouts provide poor (in the case of the stack) or likely improvable (in the case of the checkerboard) solutions to the aforementioned optimization problem. We propose a randomized greedy heuristic to construct layouts that are superior to the baseline layouts both in terms of compute power and network topology. This heuristic relies on the Hotspot simulator to evaluate the temperature of candidate layouts. Hotspot simulations are computationally intensive, and we use various techniques that make our approach feasible in spite of the Hotspot bottleneck. We present results achieved by our ivheuristic when generating 6-, 9-, and 13-chips layouts and compare these results to the checkerboard layout. Our results show that the heuristic-generated layouts are strictly superior to the baseline checkerboard layout, typically affording significantly improved compute power. Our key finding is that a randomized greedy heuristic is sufficient to generate layouts for integrated 3D multi-chip systems that afford increased performance to parallel applications when compared to previously proposed state-of-the-art layouts.