Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    An Experimental Analysis of Parallel Sorting Algorithms (1998)
    Springer
    Theory of computing systems 31 (1998), S. 135-167 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. We have developed a methodology for predicting the performance of parallel algorithms on real parallel machines. The methodology consists of two steps. First, we characterize a machine by enumerating the primitive operations that it is capable of performing along with the cost of each operation. Next, we analyze an algorithm by making a precise count of the number of times the algorithm performs each type of operation. We have used this methodology to evaluate many of the parallel sorting algorithms proposed in the literature. Of these, we selected the three most promising, Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and Valiant's flashsort, and implemented them on the connection Machine model CM-2. This paper analyzes the three algorithms in detail and discusses the issues that led us to our particular implementations. On the CM-2 the predicted performance of the algorithms closely matches the observed performance, and hence our methodology can be used to tune the algorithms for optimal performance. Although our programs were designed for the CM-2, our conclusions about the merits of the three algorithms apply to other parallel machines as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002240000083
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Accessing Nearby Copies of Replicated Objects in a Distributed Environment (1999)
    Springer
    Theory of computing systems 32 (1999), S. 241-280 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization of network resources, it is desirable that each access request be satisfied by a copy ``close'' to the requesting node. Unfortunately, it is not clear how to achieve this goal efficiently in a dynamic, distributed environment in which large numbers of objects are continuously being created, replicated, and destroyed. In this paper we design a simple randomized algorithm for accessing shared objects that tends to satisfy each access request with a nearby copy. The algorithm is based on a novel mechanism to maintain and distribute information about object locations, and requires only a small amount of additional memory at each node. We analyze our access scheme for a class of cost functions that captures the hierarchical nature of wide-area networks. We show that under the particular cost model considered (i) the expected cost of an individual access is asymptotically optimal, and (ii) if objects are sufficiently large, the memory used for objects dominates the additional memory used by our algorithm with high probability. We also address dynamic changes in both the network and the set of object copies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002240000118
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks (2000)
    Springer
    Theory of computing systems 33 (2000), S. 233-254 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n -input shuffle-unshuffle sorting networks with depth $2^{O(\sqrt{ lg lg n})} lg n$ have been discovered. These networks are the only known sorting networks of depth o( lg 2 n) that are not based on expanders, and their existence raises the question of whether a depth of O( lg n) can be achieved by any shuffle-unshuffle sorting network. In this paper we resolve this question by establishing an Ω( lg n lg lg n/lg lg lg n) lower bound on the depth of any n -input shuffle-unshuffle sorting network. Our lower bound can be extended to certain restricted classes of nonoblivious sorting algorithms on hypercubic machines.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002240010001
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A lower bound for sorting networks based on the shuffle permutation (1994)
    Springer
    Theory of computing systems 27 (1994), S. 491-508 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We prove an Ω(lg2 n/lg lgn) lower bound for the depth ofn-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial Ω(lgn) bound, while the best upper bound is given by Batcher's Θ(lg2 n)-depth bitonic sorting network. The proof technique employed in the lower bound argument may be of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01184936
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Proportionate progress: A notion of fairness in resource allocation (1996)
    Springer
    Algorithmica 15 (1996), S. 600-625 
    Details
    ISSN: 1432-0541
    Keywords: Euclid's algorithm ; Fairness ; Network flow ; Periodic scheduling ; Resource allocation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set ofn tasks andm resources, where each taskx has a rational weightx.w=x.e/x.p,0〈x.w〈1, aperiodic schedule is one that allocates a resource to a taskx for exactlyx.e time units in each interval [x.p·k, x.p·(k+1)) for allk∈N. We define a notion of proportionate progress, called P-fairness, and use it to design an efficient algorithm which solves the periodic scheduling problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940883
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Sorting-Based Selection Algorithms for Hypercubic Networks (2000)
    Springer
    Algorithmica 26 (2000), S. 237-254 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Selection, Hypercube, Parallel algorithms.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper presents several deterministic algorithms for selecting the k th largest record from a set of n records on any n -node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting algorithms for hypercubic networks. Our fastest algorithm runs in O( lg n lg * n) time, very nearly matching the trivial $\Omega(\lg n)$ lower bound. Previously, the best upper bound known for selection was O( lg n lg lg n) . A key subroutine in our O( lg n lg * n) time selection algorithm is a sparse version of the Sharesort algorithm that sorts n records using p processors, $p\geq n$ , in O( lg n ( lg lg p - lg lg (p/n) ) 2 ) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004539910011
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...