It is well-known that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying pure task parallelism or pure data parallelism. Typically, the ...
详细信息
ISBN:
(纸本)0769509908
It is well-known that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying pure task parallelism or pure data parallelism. Typically, the applications are modeled in terms of a dependence graph of coarse-grain data-parallel tasks, called a data-parallel task graph. In this paper we present a new compile-time heuristic, named Critical Path Reduction (CPR), for scheduling data-parallel task graphs. Experimental results based on graphs derived from real problems as well as synthetic graphs, show that CPR achieves higher speedup compared to other well-known existing scheduling algorithms, at the expense of some higher cost. these results are also confirmed by performance measurements of two real applications (i.e., complex matrix multiplication and Strassen matrix multiplication) running on a cluster of workstations.
In this paper we study the use of parallelism to speed up execution of Answer Set Programs (ASP). ASP is an emerging programming paradigm which combines features from constraint programming, logic programming, and non...
详细信息
ISBN:
(纸本)0769509908
In this paper we study the use of parallelism to speed up execution of Answer Set Programs (ASP). ASP is an emerging programming paradigm which combines features from constraint programming, logic programming, and non-monotonic reasoning, and has found relevant applications in areas such as planning and intelligent agents. We propose different methodologies to parallelize execution of ASP programs, and we describe a prototype which exploits one of such forms of parallelism (vertical parallelism). Performance figures are presented and analyzed along with various considerations regarding scheduling and optimization.
NASA's Information Power Grid (IPG) is an infrastructure designed to harness the power of geographically distributed computers, databases and human expertise, in order to solve large-scale realistic computational ...
详细信息
ISBN:
(纸本)0769509908
NASA's Information Power Grid (IPG) is an infrastructure designed to harness the power of geographically distributed computers, databases and human expertise, in order to solve large-scale realistic computational problems. this type of a metacomputing environment is necessary to present a unified virtual machine to application developers that hides the intricacies of a highly heterogeneous environment and yet maintains adequate security. In this paper, we present a novel partitioning scheme, called MinEX, that dynamically balances processor workloads while minimizing data movement and runtime communication, for applicationsthat are executed in a paralleldistributed fashion on the IPG. Experimental results show that MinEX is an effective load balancer in a distributed IPG environment.
Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show...
详细信息
ISBN:
(纸本)0769509908
Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show that the fundamental problems of scheduling (i) a task tree in absence of any inter-task communication on a fixed number of processors and (ii) a task tree with inter-task communication on an unbounded number of processors are NP-complete. For task trees that satisfy certain constraints, we present an optimal scheduling algorithm. the algorithm is shown optimal over a wider set of task trees than previous works.
processing and analyzing large volumes of data plays an increasingly important role in many domains of scientific research. We are developing a compiler which processes data intensive applications written in a dialect...
详细信息
One of the primary tasks in mining distributed textual data is feature extraction. the widespread digitization of information has created a wealth of data that requires novel approaches to feature extraction in a dist...
详细信息
One of the primary tasks in mining distributed textual data is feature extraction. the widespread digitization of information has created a wealth of data that requires novel approaches to feature extraction in a distributed environment. We propose a massively parallel model for feature extraction that employs unused cycles on networks of PCs/workstations in a highly distributed environment. We have developed an analytical model of the time and communication complexity of the feature extraction process in this environment based on feature extraction algorithms developed in our textual data mining research with HDDI/sup TM/ (Hierarchical distributed Dynamic Indexing). We show that speedups linear in the number of processors are achievable for applications involving reduction operations based on a novel, parallel pipelined model of execution. We are in the process of validating our analytical model with empirical observations based on the extraction of features from a large number of pages on the World Wide Web.
We propose a dynamic periodicity detector (DPD) for the estimation of periodicities in data series obtained from the execution of applications. We analyze the algorithm used by the periodicity detector and its perform...
详细信息
ISBN:
(纸本)0769509908
We propose a dynamic periodicity detector (DPD) for the estimation of periodicities in data series obtained from the execution of applications. We analyze the algorithm used by the periodicity detector and its performance on a number of data streams. It is shown how the periodicity detector is used for the segmentation and prediction of data streams. In an application case we describe how the periodicity detector is applied to the dynamic detection of iterations in parallelapplications, where the detected segments are evaluated by a speedup computation tool. We test the performance of the periodicity detector on a number of parallelized benchmarks. the periodicity detector correctly identifies the iterations of parallel structures also in the case where the application has nested parallelism. In our implementation we measure only a negligible overhead produced by the periodicity detector. We find the DPD to be useful and suitable for the incorporation in dynamic optimization tools.
Hybrid technology multithreaded architecture (HTMT) is an ambitious new architecture combining cutting edge technologies to reach petaflop performance sooner than current technology trends allow. It is a massively par...
详细信息
ISBN:
(纸本)0769509908
Hybrid technology multithreaded architecture (HTMT) is an ambitious new architecture combining cutting edge technologies to reach petaflop performance sooner than current technology trends allow. It is a massively parallel architecture with multi-threaded hardware and a multi-level memory hierarchy. Microservers provide a new perspective for viewing this memory hierarchy whereby memory is actively involved in process execution. this paper discusses the microserver memory semantics and initial HTMT execution models to analyze application at each level of the system hierarchy and to develop user-level functions for expressing this inherent concurrency and parallelism. In order to do this we studied several applications to model the control and data flow within the HTMT hierarchy and developed pseudo-code representing the user-level functions necessary to express application concurrency and parallelism.
暂无评论