This paper presents a new stochastic model for two-dimensional layouts of large size. Two problems are addressed. (1) Under the condition that the number of wires emanating from a block is Poisson distributed, determine the distribution of channel width, thus estimating the average channel width. (2) Given T tracks for each channel, determine the success probability of routing an M/spl times/M cell array chip. For both problems, closed formulas are obtained. The experiment demonstrates the effectiveness of our approach. The results can be applied to gate array, field-programmable gate array design, etc.

Recently, D. Fussell and S. Rangarajan (1989) considered performing multiple tests to achieve correct diagnosis of constant degree connection structures. They showed that the probability of correctly identifying every processor approaches one as n/spl rarr//spl infin/, where n is the number of processors in the system. In this paper, we give the performance analysis for the probabilistic diagnosis algorithm defined previously. In comparison with previous results, we first derive a different and formal proof for the analytic expression of the probability processor is correctly identified. We then show an exact analytic expression for the probability of the event that a faulty processor is correctly identified. Our result improves the previous results. Based on our new results, we finally give the asymptotic analysis for the algorithm. We demonstrate that the probability of correctly identifying every processor approaches one as n/spl rarr//spl infin/.

Huang et al, [1998] studied the diagnosis of clustered faults and wafer testing. They proposed a diagnosis algorithm for a probabilistic fault model in simple rectangular grid structures. In this paper, we extend their results and study the diagnosis algorithm for arbitrary identical degree topologies. Our results are useful and valid for a large class of topologies. We investigate the local and global performance of the algorithm under several important fault distributions: Bernoulli failure distribution, Gamma failure distribution, and exponential failure distribution. We demonstrate that the diagnosis scheme can identify almost all nodes successfully even if the percentage of fault-free units is low (much lower than 50%) while almost all units are guaranteed to be correctly identified. In addition, we show that the performance of the algorithm is insensitive to the changes of the percentage.