ISSN:1063-7192    

DOI:10.1080/10637199608915551

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

In this paper we study the problems of sorting and selection on the Distributed Memory Bus Computer (DMBC) recently introduced by Sahni. In particular we present: 1) An efficient algorithm for computing the sum ofnbits; 2) An optimalO(1) time sorting algorithm; 3) An optimal randomized logarithmic lime integer sorting algorithm; and 4) An optimal randomized constant time selection algorithm. Our algorithms will run without change in performance on many related models as well. For example, these algorithms apply to the RMBM model of Vaidyanathan et al.

ISSN:1063-7192    

DOI:10.1080/10637199608915552

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper studies relations between the parallel random access machine (PRAM) model, and the recon-figurable mesh (RMESH) model, by providing mutual simulations between the models. We present an algorithm simulating one step of an (nlglgn)-processor CRCW PRAM on ann×nRMESH with delayO(lglgn) with high probability. We use our PRAM simulation to obtain the first efficient self-simulation algorithm of an RMESH with general switches: An algorithm running on ann×nRMESH is simulated on ap×pRMESH with delayO((n/p)2× lgnlglgp) with high probability, which is optimal for allp≤n/√lgnlglgn. Finally, we consider the simulation of RMESH on the PRAM. We show that a 2 ×nRMESH can be optimally simulated on a CRCW PRAM in Θ(α(n)) time, where α(·) is the slow-growing inverse Ackermann function. In contrast, a PRAM with polynomial number of processors cannot simulate the 3 ×nRMESH in less than Ω(lgn/lglgn) expected time.

ISSN:1063-7192    

DOI:10.1080/10637199608915553

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper examines the possibility of implementing matrix operations on an array with reconfigurable optical buses (AROB). The AROB combines some of the advantages and characteristics of reconfigurable meshes and meshes with optical pipelined buses. This model is extremely flexible, as demonstrated by its ability to efficiently simulate CREW PRAMs and reconfigurable networks. A number of applications arc investigated and it is shown that many matrix operations can be implemented efficiently, reducing the time complexity and/or the cost of existing algorithms which are given for other models of parallel computation.

ISSN:1063-7192    

DOI:10.1080/10637199608915554

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper presents convex hulls algorithms for a sorted set of points on a word model reconfigurable mesh. The algorithms are designed for two input cases: sparse input (i.e. one point is given for each column) and dense input (i.e. one point is given for each processor). For sparse input, the convex hull ofnpoints can be computed inO(log2n/log2m + 1) time on ann × mreconfigurable mesh. For dense input, the convex hull ofnmpoints can be computed inO(log2n/logm + log2m) time on ann × mreconfigurable mesh. As a corollary, for every fixed ε > 0, ann × nεreconfigurable mesh is sufficient to compute the convex hull ofnpoints in constant time, and ann/2log2/3n × 2log2/3nreconfigurable mesh can compute the convex hull ofnpoints inO(log4/3n) time.

ISSN:1063-7192    

DOI:10.1080/10637199608915555

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

We propose an algorithm to solve theToken Distributionproblem, a static variant of the load balancing problem, ond-Dimensional, reconfigurable meshes with toroidal connections and side lengthn. No other algorithms have been proposed under this model of computation. We show that for token sizeT, the discrepancy Δ between the maximum and minimum number of tokens per PE can be reduced to 1 in at most In2nΔ(T +4d id)steps.

ISSN:1063-7192    

DOI:10.1080/10637199608915556

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

The generalized dominance computation (GDC) problem is stated as follows: LetA= {a1, a2, …, an} be a set of triplets, i.e.,ai= (xi, yi,fi), “⊲” be a linear order relation defined on x-components, “<” be a linear order relation defined on y-components, and “⊕” an abelian operator defined onf-components. It is required to compute for everyai∈ A, the expressionD(ai)=fj1⊕fj2⊕ … ⊕ fjk, where {j1,j2, … jk{ is the set of all indicesjsuch thataj∈ Aandxj⊲ xi, yj< yi. First, this paper presents a time-optimal algorithm to solve the GDC problem inO(√n) on a mesh connected computer of size. √n× √n. To prove the generality of our approach, we show how a number of computational geometry problems, such as ECDF (empirical cumulative distribution function) searching and two-set dominance counting, can be derived from GDC problem. Second, we define a natural extension of the GDC, called mulliple-query generalized dominance computation (MQGDC), on meshes with multiple broadcasting. By using multiple querying (MQ) paradigm of Bokka et al. |3, 4, 6| we devise a time-optimal algorithm that solves a MQGDC problem involving a setAofnitems and a setQofmqueries inO(n⅙ ⅓) on a mesh with multiple broadcasting of size √n× √n.

ISSN:1063-7192    

DOI:10.1080/10637199608915557

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Load balancing is one of the central problems that have to be solved in parallel computation. Here, the problem of distributed, dynamic load balancing for massive parallelism is addressed.

ISSN:1063-7192    

DOI:10.1080/10637199608915558

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Several architectures have been proposed to enhance point-to-point architectures with the addition of multiple bus systems. In particular, we consider an architecture for a massively parallel system where processors arc connected solely by buses. These architectures can use the power of bus technologies, providing a way to interconnect much more processors in a simple and efficient manner. In this paper we model the so-calledbus interconnection networks(BINs) by a hypergraph. We consider the gossip operation in the various proposed architectures. We focus on the hyperpath, thed-dimensional hypergrid, the hyperring, and thed-dimensional hypertorus architectures and we give corresponding algorithms for the gossiping operation. Some lower bounds are also derived.

ISSN:1063-7192    

DOI:10.1080/10637199608915559

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

LetGandHbe two simple, undirected graphs. An embedding of the graphGinto the graphHis an injective mappingffrom the vertices ofGto the vertices ofH, together with a mapping which assigns to each edge [u, v] ofGa path betweenf(u) andf(v) inH.

ISSN:1063-7192    

DOI:10.1080/10637199608915560

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor