42221171
The generalized Direction Vector I test
Abstract The Direction Vector I (DVI) test [IEEE Transaction on Parallel and Distributed Systems 4 (11) (1993) 1280] is an efficient and precise data dependence method to determine whether integer solutions exist for one-dimensional arrays with constant bounds under any given direction vectors. In this paper, we generalize the (DVI) test. The generalized Direction Vector I (GDVI) test can be applied towards determining whether integer solutions exist for one-dimensional arrays with both constant and variable limits under any given direction vectors, improving the precision and applicability of the DVI test. Experiments with benchmark showed that among 12 152 pairs of tested one-dimensional arrays consisting of the same pair of array references with different direction vectors, 2124 had their data dependence analysis amended by the GDVI test. That is, the GDVI test increases the success rate of the DVI test by approximately 17.5%.
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.
39715098
A Requirement-Based Project Estimation Approach
7900750
A Web-service oriented framework for building SCORM compatible learning management systems
Managing the large amount of learning content involved in the development of an expandable learning management system (LMS) is a critical task for most educational organizations. In designing such a system, consideration must be given not only to the requirement of instructors and students, but also to the adaptive qualities of the system itself, because of the rapidly changing software environment. Unlike most enterprises, educational organization can't afford high system maintenance. Development of a flexible, expandable and reliable learning management system is, therefore, imperative. This paper proposes a Web service oriented framework in building a sharable content object reference model (SCORM) compatible LMS. We integrated the SCORM concept with distributed computing technologies to build the components of the LMS and demonstrate how these services can be configured to create a complete system. This framework increases reusability and reduces the maintenance requirements of the LMS. It provides a way for small educational organizations, with limited resources, to build a complete SCORM compatible LMS. In such an ideal situation, the content provider not only provides the content, but also the service for the consumers of that content.
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.
22379683
Analyzing reconfigurable algorithms for managing replicated data
We analyze reconfigurable algorithms for managing replicated data to determine how often one should detect and react to failure conditions so that reorganization operations can be performed at the appropriate time to improve the availability of replicated data. We use dynamic voting as a case study to reveal design trade-offs for designing such reconfigurable algorithms and illustrate how often failure detection and reconfiguration activities should be performed so as to maximize data availability. Stochastic Petri nets are used as a tool to facilitate our analysis.
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.
56972248
FLUTE: fast lookup table based wirelength estimation technique
Wirelength estimation is an important tool to guide the design optimization process in early design stages. In this paper, we present a wirelength estimation technique called FLUTE. Our technique is based on pre-computed lookup table to make wirelength estimation very fast and very accurate for low degree nets. We show experimentally that for FLUTE, RMST, and HPWL, the average error in wirelength are 0.72%, 4.23%, and -8.71%, respectively, and the normalized runtime are 1, 1.24, and 0.16, respectively.
34361185
Dilation-5 embedding of 3-dimensional grids into hypercubes
We present an algorithm to map the nodes of a 3-dimensional grid to the nodes of its optimal hypercube on a one-to-one basis with dilation at most 5.<<ETX>>
666927
Greedy wire-sizing is linear time
In interconnect optimization by wire-sizing, minimizing weighted sink delay has been shown to be the key problem. Wire-sizing with many important objectives such as minimizing total area subject to delay bounds or minimizing maximum delay can all be reduced to solving a sequence of weighted sink delay problems by Lagrangian relaxation [1, 3]. GWSA, first introduced in [10] for discrete wire-sizing and later extended in [2] to continuous wire-sizing, is a greedy wire-sizing algorithm for the weighted sink delay problem. Although GWSA has been experimentally shown to be very efficient, no mathematical analysis on its convergence rate has ever been reported. In this paper, we consider GWSA for continuous wire sizing. We prove that GWSA converges linearly to the optimal solution, which implies that the run time of GWSA is linear with respect to the number of wire segments for any fixed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result because previously it was believed that in order to guarantee convergence, GWSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence. We demonstrate this point by showing that the minimization of maximum delay using Lagrangian relaxation can be speed up by 57.7%.
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.