Introduction

This thesis studies the problem of designing listing algorithms for families of combinatorial structures. In particular, it studies the problem of designing listing algorithms whose implementations do not use overwhelming quantities of computational resources. The computational resources that are considered are running time and storage space. Using standard terminology from complexity theory, we indicate that the time and space requirements of an algorithm are small by saying that the algorithm is “efficient”.

Section 1 of this chapter introduces our problem by defining the notion of a family of structures. It explains informally what we mean by a listing algorithm for a family of structures without discussing computational details. Section 1.2 motivates the study, describing three reasons that the problem deserves attention. Section 1.3 gives the phrase “listing algorithm” a precise meaning. In this section we specify a deterministic computational machine and a probabilistic machine. We discuss the process of implementing combinatorial listing algorithms on these machines. Section 1.4 establishes criteria which we will use to determine whether or not a given listing algorithm is efficient. The criteria will be sufficiently general that we will be able to change the computational machines that we consider (within a large class of “reasonable” machines) without changing the set of families of combinatorial structures that have efficient listing algorithms. Section 1.5 contains a synopsis of the thesis. Finally, section 1.6 contains some bibliographic remarks.

The two sections in this chapter contain work which is related to the work described in chapters 1–4. In section 5.1 we compare the computational difficulty of the listing problem with the difficulty of other computational problems involving combinatorial structures. In section 5.2 we consider a particular computational counting problem which is related to a listing problem described in chapter 4.

Comparing Listing with other Computational Problems

In this section we compare the listing problem with other computational problems involving combinatorial structures. The problems that we consider are described in [JVV 86]. For completeness, we provide a description of the problems here. Suppose that S is a family of combinatorial structures. We consider five computational problems associated with S. In each case the input is a parameter value p of S:

Problem 1 – The Existence Problem

Determine whether or not S(p) = Ø.

Problem 2 – The Construction Problem

If S(p) is non-empty then output a member of an equivalence class in S(p). Otherwise, halt without output.

Problem 3 – The Listing Problem

If S(p) is non-empty then output one representative from each equivalence class in S(p). Otherwise, halt without output.

Problem 4 – The Random Sampling Problem

If S(p) is non-empty then “randomly” choose an equivalence class in S(p) and output a member of that equivalence class. Otherwise, halt without output.

Chapter 2 described several general methods for listing combinatorial structures. In order to illustrate the methods we applied them to a few specific families of structures. In addition, we made some observations concerning the application of the methods to various classes of combinatorial families including graph properties and recursively listable families.

While the examples in chapter 2 involved particular combinatorial families, the focus of our attention was on the general listing methods. In this chapter we will shift the focus of our attention to applications. We will be interested in looking at the particular algorithms that we have developed in the course of this work and in finding out what we have learned about particular combinatorial families in the course of the work.

We start by considering a few results from chapter 2 which we will not pursue farther in this chapter. First, consider Uniform Reducer 2 which we described in subsection 2.1.2. In theorem 2 we proved that whenever Uniform Reducer 2 is combined with any efficient random sampling algorithm S-Sample for any simple family S it becomes a probabilistic polynomial delay listing algorithm for S. The listing algorithm has exponentially small failure probability. This theorem leads immediately to efficient probabilistic listing algorithms for a number of interesting families of structures since other people have developed random sampling algorithms for these families.

For example, let Sp be the family with the following definition.

The routing algorithms in Chapter 5 can be converted into efficient asynchronous algorithms by replacing the global clock with a synchronization scheme based on message passing. We also demonstrate that asynchronous fsra has low sensitivity to variations in link and processor speeds.

Introduction

The assumption of synchronism often greatly simplifies the design of algorithms, be they sequential or parallel. Many computation models — for example, RAM (“Random Access Machine”) [5] in the sequential setting and PRAM in the parallel setting — assume the existence of a global clock. But, this assumption will become less desirable as the number of processors increases. For one thing, a global clock introduces a single point of failure. A global clock also restrains each processor's degree of autonomy and renders the machine unable to exploit differences in running speed [42, 192], limiting the overall speed to, so to speak, that of the (“slowest” component instead of the “average” one, thus wasting cycles. Tight synchronization also limits the size of the parallel computer, since it takes time to distribute the clock-signal to the whole system [316].

Proceeding in epochs, our routing schemes in Chapter 5 assume synchronism. In fact, the very definition of ECS assumes a global clock to synchronize epochs. We show in this chapter that with synchronization done via message passing, ECSs can be made asynchronous without loss of efficiency and without global control. Much work has been done in this area; see, for example, [31, 32, 33].

It has long been recognized that computer design utilizing more than one processor is one promising approach — some say the only approach — toward more powerful computing machines. Once one adopts this view, several issues immediately emerge: how to connect processors and memories, how do processors communicate efficiently, how to tolerate faults, how to exploit the redundancy inherent in multiprocessors to perform on-line maintenance and repair, and so forth.

This book confronts the above-mentioned issues with two keys insights. There exist error-correcting codes that generate redundancy which is efficient in terms of the number of bits. Such redundancy is used to correct errors and erasures caused by component failures and resource limitations (such as limited buffer size). This insight comes from Michael Rabin. The next insight, due to Leslie Valiant, demonstrates the criticality of randomization in achieving communication efficiency.

We intend to make this book an up-to-date account of the information dispersal approach as it is applied to parallel computation. We also discuss related work in the general area of parallel communication and computation and provide an extensive bibliography in the hope that either might be helpful for researchers and students who want to explore any particular topic. Although materials in this book extend across several disciplines (algebra, coding theory, number theory, arithmetics, algorithms, graph theory, combinatorics, and probability), it is, the author believes, a self-contained book; adequate introduction is given and every proof is complete.

The simulation of the ideal parallel computation model, pram, on the hypercube network is considered in this chapter. It is shown that a class of pram programs can be simulated with a slowdown of O(log N) with almost certainty and without using hashing, where N denotes the number of processors. Also shown is that general pram programs can be simulated with a slowdown of O(log N) with the help of hashing. Both schemes are ida-based and fault-tolerant.

Introduction

Parallel algorithms are notoriously hard to write and debug. Hence, it is only natural to turn to ideal models that provide good abstraction. As these models do not assume any particular hardware configuration, they should have the additional benefit that programs written for them can be executed on any hardware that supports the model, similar to the situation in the sequential case where the existence of a, say, C compiler on a particular platform implies standard C programs can be compiled and executed there [370]. The PRAM (“Parallel Random Access Machine”) is one such model. It completely abstracts out the cost issue in communication and allows us to focus on the computational aspect. However, such convenience and generality is not without its price: the PRAM model, unlike the von Neumann machine model, is not physically feasible to build [369]. The simulation of PRAMs by feasible computers is therefore important and forms the major theme of this chapter.

After briefly examining the challenges facing designing ever more powerful computers, we discuss the important issues in parallel processing and outline solutions. An overview of the book is also given.

The von Neumann Machine Paradigm

The past five decades have witnessed the birth of the first electronic computer [257] and the rapid growth of the computing industry to exceed $1,000 billion (annual revenue) in the U.S. alone [162]. The demand for high-performance machines is further powered by the advent of many crucial problems whose solutions require enormous computing power: environmental issues, search for cures for diseases, accurate and timely weather forecasting, to mention just a few [271]. Moreover, although unre-lenting decrease in the feature size continues to improve the computing capability per chip, turning that into a corresponding increase in computing performance is a major challenge [152, 316]. All these factors point toward the necessity of sustained innovation in the design of computers.

That the von Neumann machine paradigm [37], the conceptual framework for most computers, considered at the system level will impede further performance gains is not hard to see. Input and output excluded, the von Neumann machine conceptually consists of a processing unit, a memory storing both programs and data, and a wire that connects the two.

In this final chapter, we briefly review techniques and concepts in fault-tolerant computing. Then we sketch the design of a fault-tolerant parallel computer, hpc (“hypercube parallel computer”), based on the results and ideas from previous chapters.

Introduction

A fault-free computer, or any human artifact, has never been built, and will never be. No matter how reliable each component is, there is always possibility, however small, that it will go wrong. Statistical principles dictate that, other things being equal, this possibility increases as the number of components increases. Such an event, if not anticipated and safe-guarded against, will eventually make the computer malfunction and lead to anything from small annoyance and inconvenience to disaster.

Recently, the same enormous decrease in hardware cost which makes parallel computers economically feasible also makes fault tolerance more affordable [297]. In other words, the low cost of hardware makes possible both high degree of fault tolerance using redundancy and high performance. Indeed, most fault-tolerant computers today employ multiple processors; see [241, 254, 317] for good surveys.

It is in the light of these backgrounds that we take this extra step toward designing a hypercube parallel computer (HPC for short). In the HPC processors are grouped into logical clusters consisting of physically close processors, and each program execution is replicated at all members of a cluster. Clusters overlap, however. The concept of cluster — logical or physical — introduces a two-level, instead of flat, organization and can be found in, for example, the Cm [344], Cedar [187], and FTPP (“Fault Tolerant Parallel Processor”) [148] computers.