Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes

By F. T. Leighton. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Evaluation & Benchmarks

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “A wide variety of access patterns (shift, any-to-any) are provided; we use the butterﬂy permutation [29] extensively.”
BCube: a high performance, server-centric network architecture for modular data centers (2009, background): “Though network interconnections have been studied for decades [11, 18], to the best of our knowledge, none of the previous structures meets the MDC requirements and the physical constraint that servers can only have a small number of network ports.”
Distributed verification and hardness of distributed approximation (2010, background): “This is done by considering the communication at the bottleneck of the network (sometimes called the bisection width [23, 25]).”
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design (2010, background): “However, all of the existing research on embedding problems for parallel processors [19], at least one of the conditions is violated (namely either load > 1 or dilation > 1 ).”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Crucially, these routing decisions can be efficiently computed (and then treated as colors) in time linear in the size of the graph [13, 91, 76, 64] or in parallel time O((log T )(2)) [74].”
Recent Advances in Graph Partitioning (2013, background): “Leighton’s book [Lei92] discusses embeddings between arrays, trees, and hypercubic topologies.”
A survey of graph layout problems (2002, background): “The following theorem gathers the optimal values of layout problems for square meshes: Theorem 2 ([26, 66, 74, 78]).”
Some problems on Cayley graphs (2008, background): “Hamiltonian paths and cycles play an important role in computer science (see [19,20]) and in combinatorial designs (see [21,22]).”
Jellyfish: Networking Data Centers Randomly (2011, background): “Moreover, carefully-structured expander graphs have been studied extensively in the high-performance computing literature [19].”