41515379
The I+ Test
The I test is an efficient and precise data dependence method to ascertain whether integer solutions exist for one-dimensional arrays with constant bounds. For one-dimensional arrays with variable limits, the I test assumes that there may exist integer solutions. In this paper, we propose the I+ test|an extended version of the I test. The I+ test can be applied towards determining whether integer solutions exist for onedimensional arrays with either variable or constant limits, improving the applicable range of the I test. Experiments with benchmark cited from EISPACK, LINPACK, Parallel loops, Livermore loops and Vector loops showed that among 1189 pairs of one-dimensional arrays tested, 183 had their data dependence analysis amended by the I+ test. That is, the I+ test increases the success rate of the I test by approximately 15:4 percent. Comparing with the Power test and the Omega test, the I+ test has higher accuracy than the Power test and shares the same accuracy with the Omega test when determining integer solutions for these 1189 pairs of one-dimensional arrays, but has much better efficiency over them.
6546539
The generalized lambda test
We generalize the /spl lambda/ test. The generalized /spl lambda/ test can be applied towards determining whether there exist data dependencies for coupled arrays with both constant and variable limits under any given direction vectors, improving the applicable range of the /spl lambda/ test. Experimental data reflecting the effect of the generalized /spl lambda/ test are also presented.
16852145
The infinity Lambda test
In this paper, WC proposed the infinity Lambda test. The infinity Lambda test can be applied IO deal with data dependence of coupled arrays with symbolic (urrknowr, at compile time) bounds. Experimental data reflecting the effect of the infinity Lambda test are also presented.
10869493
A dual-hamiltonian-path-based multicasting strategy for wormhole-routed star graph interconnection networks
Multicast is an important collective communication operation on multicomputer systems, in which the same message is delivered from a source node to an arbitrary number of destination nodes. The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we first address a dual-hamiltonian-path-based routing model with two virtual channels based on two hamiltonian paths (HPs) and a network partitioning strategy for wormhole-routed star graph networks. Then, we propose three efficient multicast routing schemes on basis of such a model. All of the three proposed schemes are proved deadlock-free. The first scheme, network-selection-based dual-path routing, selects subnetworks that are constructed either by the first HP or by the second HP for dual-path routing. The second one, optimum dual-path routing, selects subnetworks with optimum routing path for dual-path routing. The third scheme, two-phase optimum dual-path routing, includes two phases, source-to-relay and relay-to-destination. Finally, experimental results are given to show that our proposed three routing schemes outperform the unicast-based, the HP, and the single-HP-based dual-path routing schemes significantly.
13064248
Path-based multicast communication in wormhole-routed star graph multicomputers
In this paper, we propose four efficient multicast routing schemes in wormhole-routed star networks with multidestination routing capability. All of the four proposed schemes are path-based and deadlock-free. The first scheme, dual-path routing, sends the message in parallel through two independent paths. The second one, shortcut-node-based datapath routing, is similar to dual-path routing except that the routing tries to find a shortcut node to route the message as soon as possible to reduce the length of transmission path. The third one, multipath routing, is a multiple dual-path routing strategy that includes source-to-relay and relay-to-destination phases. The last scheme, proximity grouping routing, is similar to multipath routing except that in the partitioning step of source and destination nodes the relation of spatial locality of nodes is also taken into account to reduce the length of transmission paths. Finally, the experimental results are given to show that the performance based on unicast-based and traditional Hamiltonian-path routing schemes can be improved significantly by the four proposed routing schemes respectively.
37782928
A multi-dimensional version of the I test
Abstract Two-dimensional arrays with linear subscripts occur quite frequently in real programs. In general, for multi-dimensional linear arrays under constant bounds the Lambda test is an efficient data dependence method to check whether there exist real solutions. In this paper, we propose a multi-dimensional version of the I test, the multi-dimensional I test, that can be applied to testing whether there are integer solutions for multi-dimensional linear arrays under constant limits. Experiments with benchmark showing the effects of the multi-dimensional I test on testing precision and testing efficiency are also presented.
6347443
IPR: An Integrated Placement and Routing Algorithm
In nanometer-scale VLSI technologies, several interconnect issues like routing congestion and interconnect delay have become the main concerns in placement. However, all previous placement approaches optimize some very primitive interconnect models during placement. These models are far from the actual interconnect implementation in the routing stage. As a result, placement solution considered to be good by primitive interconnect models may turn out to be poor after routing. In addition, the placement may not even be routable and timing closure may not be achievable. In this paper, we propose to address the inconsistency between the placement and routing objectives by fully integrating global routing into placement. As a first attempt to this novel approach, we focus on routability issue. We call the proposed algorithm for routing congestion minimization IPR (integrated placement and routing). To ensure the algorithm to be computationally efficient, efficient placement and routing algorithms FastPlace, FastDP and FastRoute are integrated, and well-designed methods are proposed to integrate them efficiently and effectively. Experimental results show that IPR reduces overflow by 36%, global routing wirelength by 3.6%, and runtime by 36% comparing to ROOSTER, which is the previous best academic routability- driven placer.
776801
Optimizing SOC Test Resources using Dual Sequences
In this paper, we propose a new data structure called dual sequences to represent SOC test schedules. Dual sequences are used together with a simulated annealing based procedure to optimize the SOC test application time and tester resources. The problems we consider are generation of optimal test schedules for SOCs and minimizing tester memory and test channels. Results of experiments conducted on ITC’02 benchmark SOCs show the effectiveness of the proposed method.
18525423
An efficient and optimal algorithm for simultaneous buffer and wire sizing
In this paper, we consider the problem of interconnect delay minimization by simultaneous buffer and wire sizing under the Elmore delay model. We first present a polynomial time algorithm SBWS to minimize the delay of an interconnect wire. Previously, no polynomial time algorithm for the problem has been reported in the literature. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10000 segments and buffers, the CPU time is only 0.255 s. We then extend our result to handle interconnect trees. We present an algorithm SBWS-T which always gives the optimal solution. Experimental results show that SBWS-T is faster than the greedy wire sizing algorithm in practice.
10793550
Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design
In this paper, we present a very fast and accurate rectilinear Steiner minimal tree (RSMT) algorithm called FLUTE. The algorithm is an extension of the wirelength estimation approach by fast lookup table [1]. The main contribution of this paper is a new net breaking technique which is much better than the one in [1]. A scheme is also presented to allow users to control the tradeoff between accuracy and runtime.FLUTE is optimal for nets up to degree 9 and is still very accurate for nets up to degree 100. So it is particularly suitable for VLSI applications in which most nets have a degree 30 or less. We show experimentally that over 18 industrial circuits in the ISPD98 benchmark suite, FLUTE with default accuracy is more accurate than the Batched 1-Steiner heuristic and is almost as fast as a very efficient implementation of Prim's rectilinear minimum spanning tree (RMST) algorithm. By adjusting the accuracy parameter, the error can be further reduced with only a small increase in runtime (e.g., 2.7x error reduction with 2.2x runtime increase).
79941
Floorplan area minimization using Lagrangian relaxation
ABSTRACT Floorplan area minimization is an important problem because many modules have shape exibilities during the oorplanning stage. Area minimization in general non-slicing oorplan is a complicated problem. Many previous works have attempted to tackle this problem [9; 6; 5; 1] using heuristics or numerical methods but none of them can solve it optimally and e ciently. In this paper, we show how this problem can be solved optimally by a geometric programming using Lagrangian relaxation. The resulting Lagrangian relaxation subproblem is so simple that the size of each module can be found in constant time. We implemented our idea in a simulated annealing framework based on the sequence pair representation. The area minimization procedure is invoked in every iteration of the annealing process but the total execution time is still very much faster than that of the most updated previous work [4]. For a benchmark data with 49 modules, we take 19.5 hours using a 270 MHz Sun Ultra 5 while the convex programming approach in [4] takes seven days using a 250 MHz DEC Alpha. This area minimization method will be applicable to any other oorplanning algorithm which uses constraint graphs to nd module positions in the nal packing.