Search

We now turn to two application areas that have been sources of many problems to which the R-Mesh has been fruitfully applied: computational geometry and image processing. Both areas deal with relations among a large number of points. Both have problems that benefit from the R-Mesh's ability to configure its buses to conform to input data and the body of arithmetic algorithms for the R-Mesh. For image processing problems, the mesh structure naturally matches the arrangement of an array of pixels comprising an image. [ABSTRACT FROM AUTHOR]

The R-Mesh is a theoretical model that permits us to study reconfiguration as an integral tool for computation. By various limitations, enhancements, and alternatives, one can isolate the contributions of different aspects of reconfiguration. Nevertheless, one feature of the R-Mesh that cannot currently be realized is a constant delay bus of arbitrary length, spanning an almost arbitrary subset of processors. Reconfiguration is feasible, however, in a way that can lead to smaller, faster, and cheaper solutions for many problems and in a way impossible without reconfiguration. [ABSTRACT FROM AUTHOR]

Advances in optoelectronic technologies have catapulted optical interconnects and optical computing to the forefront, opening possibilities not previously considered in conventional electrical and electronic interconnection environments. A pipelined optical bus is a prime example. It differs from an electronic bus in that it employs optical fibers to transmit information. Optical signal transmission possesses two advantageous properties: unidirectional propagation and predictable propagation delay per unit length. These two properties allow synchronized concurrent access to an optical bus, creating a pipeline of messages. Processors can also broadcast and multicast on such a bus, so this architecture suits many communication-intensive applications. Researchers have proposed several models based on pipelined optical buses as parallel computing platforms. Many parallel algorithms exist for these, indicating that such systems can be very efficient for parallel computation due to the high bandwidth that comes with pipelining messages. [ABSTRACT FROM AUTHOR]

Theoretical investigations of models of computation frequently concern themselves with how models relate to each other—what can Model $$ \mathcal{A} $$ do with certain resources that Model $$ \mathcal{B} $$ cannot, or how much of a certain resource does Model $$ \mathcal{B} $$ use to simulate a given computation of Model $$ \mathcal{A} $$. Such relations exist for a range of models of computation—including Turing machines (TMs), circuits, parallel random access machines (PRAMs), and a myriad of variants—and many possible resources —typically related to time, hardware, or space (memory). Because such an extensive body of work exists, because deep understanding has been attained about many of these models, and because the computational requirements of many problems have been precisely located with respect to these models, relating a new model of computation to a standard model of computation can quickly reveal limits and possibilities that would otherwise be grasped only after years of arduous research. For example, showing the equivalence, on the one hand, of a class of LR-Mesh computations and a certain TM space class, and, on the other hand, of a class of R-Mesh computations and a different TM space class, says little directly of interest because no one is going to build a TM. It does, however, say much about a possible separation in power between the LR-Mesh and the R-Mesh because of long-studied relations between the corresponding TM space classes. [ABSTRACT FROM AUTHOR]

This chapter examines running an algorithm designed for a model of a particular size on a different-sized instance of that model or of a different model. In a general setting, this introduces the problem of scaling simulations or self-simulations, in which an instance of a model simulates a differently-sized instance of the same model. Here, we wish to show the flexibility of an implementation of a model in a given size. An algorithm may demand the number of processors to depend on the problem size. For instance, numerous algorithms in earlier chapters claimed N processors or N2 processors to solve a problem of size N. An R-Mesh implementation, however, cannot vary its number of processors as the sizes of its problems vary. If a model is scalable, then it can scale down the number of processors that an algorithm specifies to fit an available R-Mesh, at the cost of a corresponding increase in time, while maintaining the same efficiency. This problem is trivial on many models, such as a PRAM or a standard mesh, but is not so for a reconfigurable model. [ABSTRACT FROM AUTHOR]

Sorting is one of the most fundamental problems in computing and plays an important role in solving numerous problems, while providing insight to many others. Not surprisingly, sorting is perhaps one of the most widely researched problems in computing. This chapter deals primarily with sorting on the R-Mesh. The sorting algorithm we present is optimal over a large range of R-Mesh sizes. When the available R-Mesh is large enough, the sorting algorithm also suffices to solve other "easier" comparison-based problems such as merging and selection. To illustrate a case where a smaller R-Mesh solves an easier problem more efficiently than sorting, we also present a selection algorithm in this chapter. [ABSTRACT FROM AUTHOR]

Graphs provide a handy and natural way to model systems with applications that range from complex communication and transport systems, ecosystems, and programming language syntax to games, puzzles, and family trees. A good handle on techniques for graph problems translates to a rich tool box of fundamental methods for dealing with many other problems as well. In Chapter 2 (Sections 2.3.5, 2.3.6) and Chapter 3 (Section 3.1.5) we have seen that the R-Mesh is well suited to handle some graph problems. In this chapter we will build on these and other techniques developed so far to derive R-Mesh algorithms for a wide range of problems on graphs, both undirected and directed. [ABSTRACT FROM AUTHOR]

The R-Mesh readily lends itself to implementing arithmetic operations. Two features apply most strongly. The first is the ability to decompose an input into its constituent bits, then manipulate the bits individually. The second is the ability to readily route and permute hordes of data from one region of the R-Mesh to another. [ABSTRACT FROM AUTHOR]

In Chapter 2, we introduced the R-Mesh and described several algorithmic techniques for it. This model suffices for most of the discussion in this book. Enhancements to R-Meshes, however, suit some problems better, while restrictions on the R-Mesh address some practical considerations. Also, other reconfigurable models often provide a different (and sometimes equivalent) view of dynamic reconfiguration than the R-Mesh that can help in understanding dynamic reconfiguration. This chapter deals with these variations on the R-Mesh idea. [ABSTRACT FROM AUTHOR]

Chapter 1 introduced the idea of reconfiguration in terms of a simple segmentable-bus model and an informal description of the R-Mesh model. In this chapter we will build on these ideas and reconstruct the R-Mesh, this time more formally (Section 2.1). Although simple, the R-Mesh is general enough to capture most ideas in dynamic reconfiguration and will be the primary medium of expression for most of this book. In Section 2.2, we describe the pseudocode convention that we employ in this book. Following this, Section 2.3 will introduce several R-Mesh algorithmic techniques through examples spanning a wide range of applications. In the process we will also develop a palette of fundamental methods that other algorithms will invoke. [ABSTRACT FROM AUTHOR]

A reconfigurable architecture is one that can alter its components' functionalities and the structure connecting these components. When the reconfiguration is fast with little or no overhead, it is said to be dynamic. Consequently, a dynamically reconfigurable architecture can change its structure and functionality at every step of a computation. Traditionally, the term "reconfigurable" has been used to mean "dynamically reconfigurable." Indeed, most dynamically reconfigurable models (such as the reconfigurable mesh, reconfigurable multiple bus machine and reconfigurable network) do not employ the attribute "dynamic" in their names. We will use the terms "reconfigurable" and "dynamically reconfigurable" interchangeably in this book. In Chapter 11, we will discuss a form of reconfiguration called run-time reconfiguration (RTR) in which structural and functional changes in the computing device incur a significant penalty in time. [ABSTRACT FROM AUTHOR]