Due to process limitations, wiring rules are imposed by foundries on chip layout. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. Yet, traditional maze routing algorithms are not designed to handle these rules, so rule violations are corrected by post-processing and the quality of result is seriously impacted. For this reason, we propose a new maze routing algorithm capable of handling these wiring rules. The proposed algorithm is proved to find a legal shortest path with time complexity of O(n), where n is the number of grid points. Experiments with seven tight industrial cases show that the runtime of a commercial router is reduced by 2.4 times and the total wire length is also reduced by 3% on average.

Due to process limitations, wiring rules are imposed on chip layout by foundries. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. However, traditional shortest path algorithms are not properly designed for these rules. In the paper, we propose a maze routing algorithm, called MANA, capable of finding legal shortest paths under these rules. Experiments with seven industrial cases show that by handling these rules during maze routing, 94% of the violations are prevented on average, and the overall runtime of a commercial router is reduced by 71%. In addition, the total wire length is also reduced by 3% on average.

To successfully route a design, one essential requirement is to allocate sufficient routing resources. In this paper, we show that allocating routing resources based on horizontal and vertical (H/V) cut-demands can greatly improve routability especially for designs with thin areas. We then derive methods to predict the maximum H/V cut-demands and propose two cut-demand based approaches, one is to allocate routing resources considering the maximum H/V cut-demands and the other is to consolidate fragmented metal-1 routing resources for effective resource utilization. Experimental results demonstrate that the resource allocation method can precisely determine design areas and the resource consolidation method can significantly improve routability. With better routability, the routing time is about 5 times faster on average and the design area can be further reduced by 2-15%.

A mutual exclusion mechanism that is both fair and space efficient can be highly valuable for shared memory systems under time and memory constraints such as embedded real-time systems. Several algorithms that utilize only one shared variable and guarantee a certain level of fairness have been proposed. However, these use hypothetical read-modify-write operations that have never been implemented in any system. This paper presents two fair algorithms that do not use such operations, each of which uses a single additional shared variable. The proposed algorithms employ commonly available operations, fetch&store and read/write, on two shared variables. The first algorithm satisfies the bounded-bypass condition. The second is an improvement on the first that satisfies the FIFO condition, which is the most stringent fairness condition. Additionally, it is shown that achieving the bounded-bypass condition using the same set of operations requires two shared variables. Both of the algorithms are thus optimal with respect to the number of shared variables.