the distributed Consensus problem assumes that all processors in the system have some initial values;the goal is to make all non-faulty processors agree on one of these values. this paper investigates the time needed ...
详细信息
ISBN:
(纸本)0818626720
the distributed Consensus problem assumes that all processors in the system have some initial values;the goal is to make all non-faulty processors agree on one of these values. this paper investigates the time needed to reach consensus in a partially synchronous model with omission failures. In this model, the processors have no direct knowledge about time, but the time between consecutive steps of each processor is always between two known constants c1 and c2;the ratio C = c2/c1 measures the timing uncertainty in the system. Moreover, messages are delivered within time d. this paper provides an improved protocol for the above problem. When the majority of the processors is fault-free, the protocol achieves consensus in time 3(qq+1)d+Cd, where φ is the actual number of faults in a specific execution of the protocol. this will allow an increase in efficiency up to 25% over the existing protocol which requires time 4(qq+1)d+Cd.
In this paper, we present a thread-based programming model for the EM-4 hybrid dataflow machine, where parallelism and synchronization among threads of sequential execution are described explicitly by the programmer. ...
详细信息
In this paper, we present a thread-based programming model for the EM-4 hybrid dataflow machine, where parallelism and synchronization among threads of sequential execution are described explicitly by the programmer. Although EM-4 was originally designed as a dataflow machine, we demonstrate that it provides effective architectural support for a variety of programming styles, including message passing and distributed data sharing in imperative languages. Our approach allows the programmer to control the parallelism and maintain data locality explicitly to achieve high performance. EM-4 can be thought of as a multi-threaded architecture that can exploit both von Neumann and dataflow compiling technology. thread-based programming provides the first step to explore better programming/compiling technology for a hybrid dataflow ma- chine as well as EM-4.
this paper presents empirical performance of parallel algorithms for computing a spanning tree (SPT) and a minimum spanning tree (MST) of connected graphs on the Transputer and Unix systems, where processors are confi...
详细信息
Many times, routing of signal nets in the layout design of VLSI circuits turns out to be a bottleneck in designing complex chips, due to the inherent compute-intensive nature of this task. parallelprocessing of the r...
详细信息
the paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, withthe goal of minimizing the number of bends along the edges. It exhibits graphs that ...
详细信息
this paper describes the architecture of a distributed system to support crisis management. the system is designed to reduce the time required to make decisions, while maintaining decision quaility. the design combine...
详细信息
the paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, withthe goal of minimizing the number of bends along the edges. It exhibits graphs that ...
详细信息
the paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, withthe goal of minimizing the number of bends along the edges. It exhibits graphs that require Omega (n) bends in any layout, and shows that there exist optimal drawings that require Omega (n) bends and have all of them on a single edge of length Omega (n/sup 2/). On the other side of the coin, it presents a parallel algorithm that runs on a CREW PRAM in O(log n) time with n/log n processors and constructs layouts with O(n) maximum edge length and O(n/sup 2/) area. for biconnected graphs the number of bends is at most 2n+4, which is optimal in the worst-case. this work finds applications in VLSI layout, aesthetic graph drawing, and communication by light or microwave.< >
this paper considers distributed hierarchical team resource allocation in a dynamic environment. A hierarchical team of one leader and three subordinates is to process multiple types of randomly arriving tasks. Sharin...
详细信息
this paper considers distributed hierarchical team resource allocation in a dynamic environment. A hierarchical team of one leader and three subordinates is to process multiple types of randomly arriving tasks. Sharing a limited amount of renewable resources with other subordinates, each subordinate is responsible for processing a subset of tasks that arrive in his/her subsystem. the leader does not process tasks, but is responsible for coordinating subordinates' task processingthrough announcing the resource transfer plan and carrying out resource transfers among the subordinates. the objective of the team is to maximize the expected team reward through task processing. By treating the leader and subordinates as individual decisionmaking entities, a decentralized approach is adopted to model team decisionmaking and coordination processes. Having global information, the leader is assumed to develop an internal model so as to determine the team resource transfer plan. Each subordinate, on the other hand, has local information only. He/She is to obtain resource transfer plans either through the leader's announcement or by using off-line rules, and uses a local task processing model to determine task processing. By incorporating team's computation and communication limitations, separate models and solution methodologies are developed for the leader and subordinates. Comparison between model predictions and human experimental results indicates that the model has a capability to predict human team decisionmaking and coordination processes.
A prototype of a machine that utilizes parallel architecture and that was designed for a synthetic aperture radar (SAR) precision two-dimensional processing algorithm is discussed. the architecture allows drastic redu...
详细信息
A prototype of a machine that utilizes parallel architecture and that was designed for a synthetic aperture radar (SAR) precision two-dimensional processing algorithm is discussed. the architecture allows drastic reduction of the processing time involved in remote sensing applications, preserving the elaboration accuracy and flexibility. Experiments on the prototype are presented and discussed.
Graph reduction, a computational model which supports the parallel execution of functional languages, is discussed. An MIMD (multiple instruction/multiple data) machine, Flagship, which supports the graph reduction mo...
详细信息
ISBN:
(纸本)081862051X
Graph reduction, a computational model which supports the parallel execution of functional languages, is discussed. An MIMD (multiple instruction/multiple data) machine, Flagship, which supports the graph reduction model has been built. the authors investigate the formal specification and proof of an algorithm which can ensure the successful execution of a functional program in the presence of the failure of a processing element (PE) of the Flagship machine. the specifications of the algorithm, the graph reduction model, and the augmented graph reduction model, which can tolerate the failure of a PE, are described using CSP (communicating sequential processes) notation. the algebraic transformation rules of CSP are used to prove that, in the presence of PE failure, the fault-tolerant graph reduction model behaves correctly.
暂无评论