ABSTRACT
When writing a parallel algorithm on a distributed-memory platform that consists of multiple processors (e.g., a cluster of workstations with some interconnect technology), it is convenient to abstract away the physical network topology of the platform and to design algorithms using a logical topology instead. This chapter presents several parallel algorithms that are designed for use with a logical ring topology. This topology is both simple, which makes it an ideal candidate for a first look at distributed-memory parallel algorithms, and popular. Indeed, a ring is a linear interconnection network: Each processor has a single predecessor and a single successor. We will see that linear networks make for a natural decomposition of regular data structures like arrays.
