the task scheduling problem in distributed memory machines is to allocate the tasks of an application into processors in order to minimize the total execution time. this is known as an NP-complete problem. Under the c...
详细信息
ISBN:
(纸本)0769511538
the task scheduling problem in distributed memory machines is to allocate the tasks of an application into processors in order to minimize the total execution time. this is known as an NP-complete problem. Under the condition where the communication time is relatively shorter than the computation time for every task, the task duplication based scheduling (TDS) algorithm proposed by Darbha and Agrawal generates an optimal schedule. In this paper we propose an extended TDS algorithm whose optimality condition is less restricted than the TDS algorithm. Given a DAG where the condition is met, our algorithm has the time complexity of O(/V/(2)d(2)) where /V/ represents the number of tasks, and d represents the maximum degree of tasks. keywords: schedule, parallel process, task duplication, task clustering.
the concept of strong fault-tolerance was introduced to characterize the property of parallel routing [15];A network G of degree d is said strongly fault-tolerant if with at most d - 2 faulty nodes, any two nodes u an...
详细信息
ISBN:
(纸本)0769511538
the concept of strong fault-tolerance was introduced to characterize the property of parallel routing [15];A network G of degree d is said strongly fault-tolerant if with at most d - 2 faulty nodes, any two nodes u and v in G are connected by min{deg(f)(u), deg(f)(v)} node-disjoint paths, where degf (u) and degf(v) are the numbers of non-faulty non-faulty neighbors of the nodes u and v in G, respectively. We show that the hypercube networks are strongly fault-tolerant and develop an algorithm that constructs the maximum number of node-disjoint paths in a hypercube network with faults. Our algorithm is optimal in terms of time and length of node-disjoint paths.
this paper presents a distributed implementation of the Structured Gamma programming language, a language based on the Gamma multiset rewriting paradigm Structured Gamma offers, in addition to the advantages introduce...
详细信息
ISBN:
(纸本)0769511538
this paper presents a distributed implementation of the Structured Gamma programming language, a language based on the Gamma multiset rewriting paradigm Structured Gamma offers, in addition to the advantages introduced by Gamma implicit concurrent behavior and a type system where not only types themselves are defined but also the automatic verification of user defined types at compilation time. Problems and mechanisms involved in a MPI-based implementation of Structured Gamma using a type checking engine based on MGU - Most General Unifier are investigated.
parallelalgorithms for solving nonlinear systems are studied. Non-stationary parallelalgorithms based on the Newton method are considered. Convergence properties of these methods are studied when the matrix in quest...
详细信息
ISBN:
(纸本)3540419993
parallelalgorithms for solving nonlinear systems are studied. Non-stationary parallelalgorithms based on the Newton method are considered. Convergence properties of these methods are studied when the matrix in question is either monotone or an H-matrix. In order to illustrate the behavior of these methods, we implemented these algorithms on two distributed memory multiprocessors. the first platform is an Ethernet network of five 120 MHz Pentiums. the second platform is an IBM RS/6000 with8 nodes. Several versions of these algorithms are tested. Experiments show that these algorithms can solve the nonlinear system in substantially less time that the current (stationary or non-stationary) parallel nonlinear algorithms based on the multisplitting technique.
A novel parallel architecture for estimating computationally intensive 4th-order cumulants is presented. Different from most systolic array implementations, a MIMD array processor is used to efficiently compute the cu...
详细信息
A formal approach, called Manufacturing Algebra, to model complex manufacturing process has been suggested in previous publications. the approach is based on the key concepts of object types, locations and manufacturi...
详细信息
ISBN:
(纸本)0780372417
A formal approach, called Manufacturing Algebra, to model complex manufacturing process has been suggested in previous publications. the approach is based on the key concepts of object types, locations and manufacturing operations enriched with an algebra for building complex operations as algebraic series-parallel compositions. In this paper a review of the Manufacturing Algebra is given, and some new advancements are provided.
We have developed and evaluated two parallelization schemes for a tree-based k-means clustering method on shared memory machines. One scheme is to partition the pattern space across processors. We have determined that...
详细信息
In this work we describe several portable sequential and parallelalgorithms for solving the inverse eigenproblem for Real Symmetric Toeplitz matrices. the algorithms are based on Newton’s method (and some variations...
详细信息
In this paper, a parallel Object Collection (POC) model is introduced to support data parallelism in a parallel object-oriented system. this model is based on the idea of data partitioning and method replication. To a...
详细信息
ISBN:
(纸本)0769511538
In this paper, a parallel Object Collection (POC) model is introduced to support data parallelism in a parallel object-oriented system. this model is based on the idea of data partitioning and method replication. To achieve load-balancing, partition objects are dynamically migrated at runtime according to the system load situation. A threshold-based strategy is used in the dynamic load-balancing. To avoid over-convergence of load during partition object migration, a new destination node selection algorithm is proposed. the threshold values used in the algorithm are also adaptively adjusted to better reflect the fluctuation of the load during execution. To evaluate the performance of the dynamic load balancing algorithm, simulation experiments are conducted. the simulation results are reported and discussed in the paper.
the proceedings contain 130 papers. the special focus in this conference is on parallelprocessing. the topics include: Software component technology for high performance parallel and grid computing;connecting computa...
ISBN:
(纸本)3540424954
the proceedings contain 130 papers. the special focus in this conference is on parallelprocessing. the topics include: Software component technology for high performance parallel and grid computing;connecting computational requirements with computing resources;a tool for binding to threads processors;a distributed object infrastructure for interaction and steering;optimal polling for latency-throughput tradeoffs in queue-based network interfaces for clusters;performance prediction of data-dependent task parallel programs;the hardware performance monitor toolkit;via communication performance on a gigabit Ethernet cluster;group-based performance analysis for multithreaded SMP cluster applications;exploiting unused time slots in list scheduling considering communication contention;an evaluation of partitioners for parallel SAMR applications;load balancing on networks with dynamically changing topology;approximation algorithms for scheduling independent malleable tasks;load redundancy elimination on executable code;using a swap instruction to coalesce loads and stores;data-parallel compiler support for multipartitioning;parallel and distributed databases, data mining and knowledge discovery;an experimental performance evaluation of join algorithms for parallel object databases;a classification of skew effects in parallel database systems;experiments in parallel clustering with DBSCAN;analysis of the cycle structure of permutations;scanning biosequence databases on a hybrid parallel architecture;experiences in using MPI-Io on top of GPFS for the IFS weather forecast code;improving conditional branch prediction on speculative multithreading architectures;performances of a dynamic threads scheduler and self-stabilizing neighborhood unique naming under unfair scheduler.
暂无评论