A simulation program has been developed to calculate the power-spectral density of thin avalanche photodiodes, which are used in optical networks. The program extends the time-domain analysis of the dead-space multipl...
详细信息
A simulation program has been developed to calculate the power-spectral density of thin avalanche photodiodes, which are used in optical networks. The program extends the time-domain analysis of the dead-space multiplication model to compute the autocorrelation function of the APD impulse response. However, the computation requires a large amount of memory space and is very time consuming. We describe our experiences in parallelizing the code using both MPI and OpenMP. Several array partitioning schemes and scheduling policies are implemented and tested Our results show that the OpenMP code is scalable up to 64 processors on an SGI Origin 2000 machine and has small average errors.
Presented in this paper are low-power, reconfigurable adaptive CDMA multiuser receiver architectures developed via dynamic algorithmic transforms (DAT). The architectures achieve low-power operation via run-time recon...
详细信息
Presented in this paper are low-power, reconfigurable adaptive CDMA multiuser receiver architectures developed via dynamic algorithmic transforms (DAT). The architectures achieve low-power operation via run-time reconfiguration of receiver complexity to match the requirements of a time-varying multiuser channel. Simulation results with 0.25 /spl mu/m, 2.3 V CMOS technology parameters indicate that the proposed architectures have high resistance to the near-far problem, and can achieve up to 60.4% in power savings compared to architectures without DAT depending on the interference situation.
The problem of scheduling a weighted directed acyclic graph (DAG) to a set of homogeneous processors to minimize the completion time has been extensively studied. The NP-completeness of the problem has instigated rese...
详细信息
The problem of scheduling a weighted directed acyclic graph (DAG) to a set of homogeneous processors to minimize the completion time has been extensively studied. The NP-completeness of the problem has instigated researchers to propose a myriad of heuristic algorithms. While these algorithms are individually reported to be efficient, it is not clear how effective they are and how well they compare against each other. A comprehensive performance evaluation and comparison of these algorithms entails addressing a number of difficult issues. One of the issues is that a large number of scheduling algorithms are based upon radically different assumptions, making their comparison on a unified basis a rather intricate task. Another issue is that there is no standard set of benchmarks that can be used to evaluate and compare these algorithms. Furthermore, most algorithms are evaluated using small problem sizes, and it is not clear how their performance scales with the problem size. The authors first provide a taxonomy for classifying various algorithms into different categories according to their assumptions and functionalities. They then propose a set of benchmarks which are of diverse structures without being biased towards a particular scheduling technique and still allow variations in important parameters. They have evaluated 15 scheduling algorithms, and compared them using the proposed benchmarks. Based upon the design philosophies and principles behind these algorithms, they interpret the results and discuss why some algorithms perform better than the others.
Obtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose sea...
详细信息
Obtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose search-based algorithms for determining optimal schedules for moderately large problem sizes. The first algorithm which is based on the A* search technique uses a computationally efficient cost function for guiding the search with reduced complexity. We propose a number of state-pruning techniques to reduce the size of the search space. For further lowering the complexity, we parallelize the search. The parallel version is based on reduced interprocessor communication and is guided by static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but takes considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions for medium to moderately large problems while the approximate algorithm is a useful alternative if slightly degraded solutions are acceptable.
Data staging is an important data management problem for a distributed heterogeneous networking environment, where each data storage location and intermediate node may have specific data available, storage limitations...
详细信息
Data staging is an important data management problem for a distributed heterogeneous networking environment, where each data storage location and intermediate node may have specific data available, storage limitations, and communication links. Sites in the network request data items and each item is associated with a specific deadline and priority. It is assumed that not all requests can be satisfied by their deadline. The work concentrates on solving a basic version of the data staging problem in which all parameter values for the communication system and the data request information represent the best known information collected so far and stay fixed throughout the scheduling process. A mathematical model for the basic data staging problem is introduced. Then, a multiple-source shortest-path algorithm based heuristic for finding a suboptimal schedule of the communication steps for data staging is presented. A simulation study is provided, which evaluates the performance of the proposed heuristic. The results show the advantages of the proposed heuristic over two random based scheduling techniques. This research, based on the simplified static model, serves as a necessary step toward solving the more realistic and complicated version of the data staging problem involving dynamic scheduling, fault tolerance, and determining where to stage data.
parallel generic algorithms (PGAs) have been developed to reduce the large execution times that are associated with serial generic algorithms (SGAs). They have also been used to solve larger problems and to find bette...
详细信息
parallel generic algorithms (PGAs) have been developed to reduce the large execution times that are associated with serial generic algorithms (SGAs). They have also been used to solve larger problems and to find better solutions. A comparative analysis of five different coarse-grained PGAs is conducted using the traveling salesman problem as the basis of this case study. To make fair comparisons, all of these PGAs are based on the same baseline SGA, implemented on the same parallel machine (IBM SP2), tested on the same set of traveling salesman problem instances, and started from the same set of initial populations. As a result of the experiments conducted in this study, a particular PGA that combines a new subtour technique with a known migration approach is identified to be the best for the traveling salesman problem among the five PGAs being compared.
Discusses the use of run-time feedback for optimizing the execution of parallel computations. Four levels of feedback are distinguished and the applicability and limitations of each are discussed. A two-part schedulin...
详细信息
Discusses the use of run-time feedback for optimizing the execution of parallel computations. Four levels of feedback are distinguished and the applicability and limitations of each are discussed. A two-part scheduling paradigm known as SEDIA (Static Exploration/Dynamic Instantiation and Activation) that addresses these limitations to perform robust scheduling in the presence of variant run-time behaviour is introduced. A key component of this scheduling paradigm is an abstract model of run-time information fidelity, which has evolved from our previous work in the area of trace recovery, employing control-theoretic concepts.
Increasingly, feedback of measured run-time information is being used in the optimization of computation execution. Because of this, the need for a model relating the static view of a computation to its runtime varian...
详细信息
A large collection of texts may be reached through the Internet and this provides a powerful platform from which common-sense knowledge may be gathered. This paper presents a system that contains a core knowledge base...
Increasingly, feedback of measured run-time information is being used in the optimization of computation execution. This paper introduces a model relating the static view of a computation to its run-time variance that...
详细信息
Increasingly, feedback of measured run-time information is being used in the optimization of computation execution. This paper introduces a model relating the static view of a computation to its run-time variance that is useful in this context. A notion of uncertainty is then used to provide bounds on key scheduling parameters of the run-time computation. To illustrate the relationship between fidelity in measured information and minimum schedulable, grain size, we apply the bounds to three existing parallel architectures for the case of run-time variance caused by monitoring intrusion. We also outline a hybrid static-dynamic scheduling paradigm-SEDIA-that uses the model of uncertainty to optimize computation for execution in the presence of run-time variance from sources other than monitoring intrusion.
暂无评论