Placement with alignment and performance constraints using the B*-tree representation

To facilitate sequential data transfer (e.g., bus or pipeline signals) and reduce bounded net delay (as well as total wirelength), it is desired to align circuit blocks one by one and constrain the blocks within a certain bounding box. In this paper, we handle the placement with alignment and performance (delay) constraints using the B*-tree representation. We first explore the feasibility conditions with the alignment and performance constraints, and then propose algorithms that can guarantee a feasible placement with alignment constraints and generate a good placement with performance constraints during each operation. In particular, our method is the first algorithm to achieve the amortized linear-time complexity for evaluating a placement with the alignment and performance constraints. Experimental results based on the MCNC benchmark with the constraints show that our method significantly outperforms the previous work.