This paper addresses the use of parallel simulation techniques to speedup the simulation of multistage interconnection networks. The conventional null-message approach to resolving deadlock problem in conservative sim...
详细信息
This paper addresses the use of parallel simulation techniques to speedup the simulation of multistage interconnection networks. The conventional null-message approach to resolving deadlock problem in conservative simulation is based on a lookahead mechanism. For some application domains, unfortunately, the lookahead information is not available. Consequently, the simulation using null messages will be trapped in a livelock. We propose a deadlock/livelock free scheme using null messages, but without the guaranteed lookahead, to coordinate the simulation, and different partitioning techniques for mapping of the simulation program onto multicomputers. A flushing mechanism to address the combinatoric explosion of using null-message in conservative simulation is also discussed. Our analysis shows that the proposed flushing mechanism effectively reduces the number of null messages from exponential to linear.
M.J. Maher (1987) proposed the ALPS class of committed-choice languages, which can be seen as a further development of concurrent logic programming languages in the direction of CLP(X). However, due to the lack of OR-...
详细信息
ISBN:
(纸本)0818665076
M.J. Maher (1987) proposed the ALPS class of committed-choice languages, which can be seen as a further development of concurrent logic programming languages in the direction of CLP(X). However, due to the lack of OR-nondeterminism, ALPS is a class of declarative algorithmic programming languages. In this paper, we present the FENG class of concurrent constraint logic programming languages and give its soundness and completeness results. With the novel feature of constraint based nondeterminism, FENG enriches the semantics of the ALPS and CLP(X). One of the features of FENG is that it supports constraint bared nondeterminism. For some class of programs, this improves the efficiency of program execution. FENG reveals a direction for data-parallel implementations of constraint logic programs. This has been confirmed by our experience in design and implementation of Firebird, a restriction of FENG, on the massively parallel machine DECmpp.< >
A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The no...
详细信息
A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The nodes communicate with each other by exchanging packets through shared buses in CREW manner. Suppose that each node initially contains a piece of information called a token. A gossiping problem is the routing problem of exchanging tokens among all nodes in the computer, which has been studied extensively as a basic communication scheme for sharing information among nodes in a parallel computer. In this paper, we propose three gossiping algorithms for mesh-bus computers assuming that each packet can carry at most (≥ 1) tokens in a step. It is shown that by selecting the fastest algorithm among them, for each , a lower bound on the gossiping time can be attained asymptotically.
The proceedings contains 65 papers on systems science. Topics discussed include databases, computer systems, computer programming, algorithms, computer programming languages, computer operating systems, program compil...
详细信息
ISBN:
(纸本)0818650605
The proceedings contains 65 papers on systems science. Topics discussed include databases, computer systems, computer programming, algorithms, computer programming languages, computer operating systems, program compilation, parallel systems, computer software, system recovery, data storage and computer architectures.
We are pursuing research on programming languages for massively parallel processing. The objective of the research is the following two points according to the top level research objective of our Massively parallel Pr...
详细信息
We are pursuing research on programming languages for massively parallel processing. The objective of the research is the following two points according to the top level research objective of our Massively parallel Processing Principle Research Project: firstly to develop a prototype of a massively parallelprogramming language and compiler system, which is competitive to commercial language systems like data parallel C, Fortran D or HPF; and secondly to explore a massively parallel computation model, and design an experimental language as an implementation of the newly explored massively parallel computation model.< >
A collective communication library for parallel computers includes frequently used operations such as broadcast, reduce, scatter, gather, concatenate, synchronize, and shift. Such a library provides users with a conve...
详细信息
ISBN:
(纸本)0818656026
A collective communication library for parallel computers includes frequently used operations such as broadcast, reduce, scatter, gather, concatenate, synchronize, and shift. Such a library provides users with a convenient programming interface, efficient communication operations, and the advantage of portability. A library of this nature, the Collective Communication Library (CCL), intended for the line of scalable parallel computer products by IBM, has been designed. CCL is part of the parallel application programming interface of the recently announced IBM 9076 Scalable POWERparallel System 1 (SP1). In this paper, we examine several issues related to the functionality, correctness, and performance of a portable collective communication library while focusing on three novel aspects in the design and implementation of CCL: (i) the introduction of process groups, (ii) the definition of semantics that ensures correctness, and (iii) the design of new and tunable algorithms based on a realistic point-to-point communications model.
In this paper, we shall present several algorithms for determining the maximum number of vertex connectivity, testing k-vertex connectivity, determining the maximum number of vertex disjoint s-t paths and finding k-ve...
详细信息
In this paper, we shall present several algorithms for determining the maximum number of vertex connectivity, testing k-vertex connectivity, determining the maximum number of vertex disjoint s-t paths and finding k-vertex disjoint s-t paths problems on a permutation graph, respectively. We first give several O(n2) time sequential algorithms for determining the maximum number of vertex connectivity, testing k-vertex connectivity and determining the maximum number of vertex disjoint s-t paths problems, respectively. Then, an O(kn2) time algorithm for finding k-vertex disjoint s-t paths problem on a permutation graph is also proposed. Moreover, we also derive the corresponding parallel algorithms for these problems from the proposed sequential algorithms. On the EREW PRAM model, we first propose several O(log n) time optimal speed-up parallel algorithms for determining the maximum number of vertex connectivity, testing k-vertex connectivity and determining the maximum number of vertex disjoint s-t paths problems, all with O(n2/log n) processors, respectively. Then, an O(n log n) time parallel algorithm for finding k-vertex disjoint s-t paths problem using O(n2/log n) processors is also developed, where k is a fixed integer.
We know that a significant advantage of content addressable memory (CAM) is that operations are performed locally, thus it can eliminate the problem of bottleneck between processor and memory. In this paper, we propos...
详细信息
We know that a significant advantage of content addressable memory (CAM) is that operations are performed locally, thus it can eliminate the problem of bottleneck between processor and memory. In this paper, we propose a CAM-based associative processing processor (HAPP) which is able to combine with a general processor to form an array-processor system, and besides retrieval operations, it can assist the general processor to manipulate nested loop structure with data-flow dependence for achieving high speedup in this system. We enumerate some problems of applying HAPP into a computer system to deal with nested loop structure, and the methods we used to resolve them. Also we compare HAPP with a parallel machine, BBN TC2000, to prove that HAPP gains a less communication penalty when the number of data items access of BBN TC2000 surpasses penalty plane.
National Research Center for Intelligent Computing Systems (NCIC) is the unique national hi-tech R/D center for advanced computing technology in China. We introduce China's Hi- Tech R&D Programme (863 programm...
详细信息
ISBN:
(纸本)0818665076
National Research Center for Intelligent Computing Systems (NCIC) is the unique national hi-tech R/D center for advanced computing technology in China. We introduce China's Hi- Tech R&D Programme (863 programmes) and NCIC, and we report on the state of the art of parallel processing at NCIC. The article discusses the key technologies being exploited by the representative Chinese R & D teams and the wide applications of parallel computers in China. The key technologies in parallel processing we are attacking are reported and include wormhole routing and other efficient switching techniques, the Easter series, MPP systems, the Dawning series symmetric and multi-thread multiprocessor, parallel operating systems and parallel file systems, parallel compilers and efficient programming tools. Future research directions at NCIC are also mentioned.< >
In this paper, we shall first introduce the single step searching problem which is defined as follows: We are given a graph where each vertex is associated with a weight. Assume that every edge of graph is of equal le...
详细信息
In this paper, we shall first introduce the single step searching problem which is defined as follows: We are given a graph where each vertex is associated with a weight. Assume that every edge of graph is of equal length. A fugitive can may be hidden in any edge. We are asked to assign searchers to vertices to search the entire graph in one step such that no fugitive can escape. The cost of a searching plan is related to the weights of the vertices in which the searchers are initially located. Our goal is to minimize the cost of the searching plan. A parallel algorithm based upon The EREW model is proposed to solve this problem. This algorithm applies the tree contraction technique. The critical point is that we have to transform a general tree to a binary tree including pseudo nodes in order to apply this tree contraction technique. A new algorithm is devised to solve the problem on the transformed binary tree. It can be proved that this new algorithm is correct as it produces a correct solution for the original tree. Our algorithm has an optimal speed up.
暂无评论