Beyond-die (commented by Yu Hu)

l Muhammet Mustafa Ozdal, Martin D. F. Wong and Philip S. Honsinger, "Simultaneous escape routing and layer assignment for dense PCBs ".

Comments: This paper mainly discussed package routing for the pins between two dies (e.g. PCB).

The objective of this problem is to minimize the number of crossings between wires connecting pins in both dies, in the same time no con°icts can occur in the escape routing in the individual die. The authors formulate this problem as a longest path with forbidden pairs (LPFP) problem, which is an NP-Hard problem. Two algorithms, an exact one and a random based approximate but faster one, are proposed to handle LPFP problem.

l Muhammet Mustafa Ozdal, Martin D. F. Wong and Philip S. Honsinger, "AN ESCAPE ROUTING FRAMEWORK FOR DENSE BOARDS WITH HIGH-SPEED DESIGN CONSTRAINTS"

Comments: This paper follows the work of the last paper. The main contribution is that more routing patterns are added into consideration so that a larger searching space is explored. To handle the additional routing patterns, an improvement of the algorithm is also given.

l Muhammet Mustafa Ozdal, Martin D. F. Wong and Philip S. Honsinger, "OPTIMAL ROUTING ALGORITHMS FOR PIN CLUSTERS IN HIGH-DENSITY MULTICHIP MODULES"

Comments: Traditionally, people treat the package routing area as a regular rectangle, but sometimes, pin clusters in package has irregular shapes due to the limitation of blind or buried vias to span all layers of the package. This paper study on the pin clusters who have a rectilinear convex boundaries and address the problem how the positions of escape terminals on a convex boundary affect the overall routability. An optimal algorithm to select the maximal subset of nets that are routable outside the boundary is proposed, and then another optimal algorithm to escape all net in this set out of the package is presented.

l Horiuchi, M.; Yoda, E.; Takeuchi, Y., "Escape routing design to reduce the number of layers in area array packaging".

Comments: Focused on the escape routing design within one die, this paper studies on the e®ect of the escape routing style on the layer number reduction. The authors compare the conventional escape routing (escape from the outer row to inner row) and the hybrid channel routing (based on preferential routing along the vertical rows) and different settings of the hybrid channel are discussed. The main conclusion is, the layer counts can be decreased for a given identical area array pad matrix depending on a routing design and nothing change in the manufacturing process, such as reduce the wire width, is required with this procedure.

l Rui Shi, Hongyu Chen, C. K. Cheng et al, "Layer Count Reduction for Area Array Escape Routing"

Comments: Focusing on layer count reduction for the I/O pins escape routing, this paper analyzes the influence of pins escape sequence (escape routing pattern) to the layer count. By analyzing the escape bottleneck in an area array using maximum flow algorithm, author identify that the two-sided method is the most effective way to reduce the number of escape routing layers. However, no performance issues are considered in this paper.

l Jinjun Xiong et at, "Constraint Driven I/O Planning and Placement for Chip-package Co-design"



l Bruce Riggins, "It's Not All About the FGPA Anymore"