MRNet is an infrastructure that provides scalable multicast and data aggregation functionality for distributed tools. While evaluating MRNet's performance and scalability, we learned several important lessons abou...
详细信息
ISBN:
(纸本)0769521320
MRNet is an infrastructure that provides scalable multicast and data aggregation functionality for distributed tools. While evaluating MRNet's performance and scalability, we learned several important lessons about benchmarking large-scale, distributed tools and middleware. first, automation is essential for a successful benchmarking effort, and should be leveraged whenever possible during the benchmarking process. Second, microbenchmarking is invaluable not only for establishing the performance of low-level functionality, but also for design verification and debugging. Third, resource management systems need substantial improvements in their support for running tools and applications together. Finally, the most demanding experiments should be attempted early and often during a benchmarking effort to increase the chances of detecting problems with the tool and experimental methodology.
This paper examines several heuristic algorithms for the maximum allowable workload (MAW) problem for real-time systems with tasks having variable workloads. Briefly, the problem concerns the allocation of n tasks to ...
详细信息
ISBN:
(纸本)0769521320
This paper examines several heuristic algorithms for the maximum allowable workload (MAW) problem for real-time systems with tasks having variable workloads. Briefly, the problem concerns the allocation of n tasks to m processors, where each task t is characterized by a function t.r(w) that gives the running time of the task in terms of its workload (or input size) w. The objective of the maximum allowable workload problem is to find an allocation of tasks to processors so that the allocation is feasible (no task misses its deadline) when each task is given a work-load of w or smaller and w is maximized. This optimization problem uses a robustness measure that is closely related to the MAIL (maximum allowable increase in load) metric recently proposed by Gertphol et. al. The main contribution of this paper is the the comparison of several heuristic algorithms for the MAW-RMS problem. Hillclimbing, random search, simulated annealing, and first-fit heuristics are presented and evaluated via simulation. As we show here, the first-fit greedy heuristic produces solutions of a reasonable quality compared to the other algorithms. In addition, we demonstrate the applicability of our model in air defense systems.
With the arrival of the new computing paradigm in addressing autonomous systems for heterogeneous distributed architectures, distributed component technologies face challenges ahead. One of the key issues will be how ...
详细信息
ISBN:
(纸本)0769521320
With the arrival of the new computing paradigm in addressing autonomous systems for heterogeneous distributed architectures, distributed component technologies face challenges ahead. One of the key issues will be how one can have component models adapt and respond to environment changes autonomously. In our research work, we argue that additional annotation specifications for components are needed to advance this process. In this paper, we first present additional annotation specifications for components. This information can then be retrieved by Java introspection and represented in DAML+OIL language, which is based on the RDF schema and the XML syntax. Based on the specifications, we then present a Component Management Service (CMS) model and architecture to address the specification and composition issues of components on heterogeneous distributed architectures. Experimental results show significant performance improvements with our support of component adaptations in all cases. Our work presents a major advance for areas related to specifications and compositions of distributed components.
In this paper, we treat the linkage disequilibrium, used to discover haplotypes, candidate to explain multi-factorial diseases such as diabetes or obesity, as an optimization problem where a given objective function h...
详细信息
ISBN:
(纸本)0769521320
In this paper, we treat the linkage disequilibrium, used to discover haplotypes, candidate to explain multi-factorial diseases such as diabetes or obesity, as an optimization problem where a given objective function has to be optimized. In order to determine what kind of algorithm will be able to solve this problem, we first study the specificities and the structure of the problem. Results of this study show that exact algorithms are not adapted to this specific problem and lead us to the development of a parallel dedicated adaptive multipopulation genetic algorithm that is able to find several haplotypes of different sizes. After describing the biological problem, we present the dedicated genetic algorithm, its specificities, such as the use of several populations and its advanced mechanisms such as the adaptive choice of operators, random immigrants, and its parallel implementation. We give results on a real dataset.
One of the barriers that prevents the expansion and adoption of Grid technologies is the lack of a standard programming paradigm to port existing applications among different environments. The distributed Resource Man...
详细信息
The technique of replicating frequently-accessed files to other nodes has been widely used in a high-performance distributed system to reduce the load of the nodes hosting these files. Traditional file replication alg...
详细信息
ISBN:
(纸本)0769521320
The technique of replicating frequently-accessed files to other nodes has been widely used in a high-performance distributed system to reduce the load of the nodes hosting these files. Traditional file replication algorithms rely on the analysis of client-access logs to determine the location of the replicated nodes. In this paper, we present LessLog, a logless file replication algorithm, developed for a peer-to-peer distributed system. We first construct a lookup tree for each node. LessLog uses bitwise operations to determine the location of the replicated node without any client-access history. In addition, each replication is guaranteed to reduce the workload of the replicating node by half. A fault-tolerant LessLog model is also presented. The experimental results show that LessLog successfully and efficiently reduces the load of overloaded nodes.
Hash-basedjoin is a compute- and memory-intensive algorithm. It achieves good performance and scales well to large datasets, if sufficient memory is available to hold the hash table and the distribution of computing l...
详细信息
ISBN:
(纸本)0780321754
Hash-basedjoin is a compute- and memory-intensive algorithm. It achieves good performance and scales well to large datasets, if sufficient memory is available to hold the hash table and the distribution of computing load across nodes is balanced. In this paper we compare three adaptive algorithms that start with a partitioning of the hash table across a group of nodes and expand during the hash table building phase to additional resources, when memory on a node is used up. The split-based algorithm partitions the hash table range assigned to the node, on which memory is full, into two segments and assigns one of the segments to a new node in the system. The replication-based algorithm replicates the hash table range on a new node. The hybrid algorithm combines the first and second strategies in order to address each strategy's short comings. We perform an experimental performance evaluation of these algorithms on a PC cluster Our results show that among the three algorithms, in most cases the hybrid algorithm either performs close to the better of the two or is the best algorithm.
As the number of processors for multi-teraflop systems grows to tens of thousands, with proposed petaflops systems likely to contain hundreds of thousands of processors, the assumption of fully reliable hardware has b...
详细信息
ISBN:
(纸本)0769521320
As the number of processors for multi-teraflop systems grows to tens of thousands, with proposed petaflops systems likely to contain hundreds of thousands of processors, the assumption of fully reliable hardware has been abandoned. Although the mean time between failures for the individual components can be very high, the large total component count will inevitably lead to frequent failures. It is therefore of paramount importance to develop new software solutions to deal with the unavoidable reality of hardware faults. In this paper we will first describe the nature of the failures of current large-scale machines, and extrapolate these results to future machines. Based on this preliminary analysis we will present a new technology that we are currently developing, buffered coscheduling, which seeks to implement fault tolerance at the operating system level. Major design goals include dynamic reallocation of resources to allow continuing execution in the presence of hardware failures, very high scalability, high efficiency (low overhead), and transparency - requiring no changes to user applications. Preliminary results show that this is attainable with current hardware.
AIAC algorithms (Asynchronous Iterations Asynchronous Communications) are a particular class of parallel iterative algorithms. Their asynchronous nature makes them more efficient than their synchronous counterparts in...
详细信息
ISBN:
(纸本)0769521320
AIAC algorithms (Asynchronous Iterations Asynchronous Communications) are a particular class of parallel iterative algorithms. Their asynchronous nature makes them more efficient than their synchronous counterparts in numerous cases as has already been shown in previous works. The first goal of this article is to compare several parallel programming environments in order to see if there is one of them which is best suited to efficiently implement AIAC algorithms. The main criterion for this comparison consists in the performances achieved in a global context of grid computing for two classical scientific problems. Nevertheless, we also take into account two secondary criteria which are the ease of programming and the ease of deployment. The second goal of this study is to extract from this comparison the important features that a parallel programming environment must have in order to be suited for the implementation of AIAC algorithms.
There are two main approaches for designing parallel language. The first approach states that parallel computing demands new programming concepts and radical intellectual changes regarding the way we think about progr...
详细信息
ISBN:
(纸本)0769522106
There are two main approaches for designing parallel language. The first approach states that parallel computing demands new programming concepts and radical intellectual changes regarding the way we think about programming, as compared to sequential computing. Therefore, the design of such a parallel language must present new constructs and new programming methodologies. The second approach states that there is no need to reinvent the wheel, and serial languages can be extended to support parallelism. The motivation behind this approach is to keep the language as friendly as possible for the programmer who is the main bridge toward wider acceptance of the new language. In this paper we present a qualitative evaluation of two contemporary parallel languages: OpenMP-C and Unified parallel C (UPC). Both are explicit parallel programming languages based on the ANSI C standard. OpenMP-C was designed for shared-memory architectures and extends the base-language by using compiler directives that annotate the original source-code. On the other hand, UPC was designed for distribute-shared memory architectures and extends the base-language by new parallel constructs. We deconstruct each parallel language into its basic components, show examples, make a detailed analysis, compare them, and finally draw some conclusions.
暂无评论