26607
Firehose Architectures for Free-Space Optically Interconnected VLSI Circuits
Free-space optical interconnects will soon be able to provide input/output bandwidths to a VLSI chip in excess of a terabit per second. The successful application of this technology to parallel distributed processing systems depends on the development of high-bandwidth interconnects and the ability of the architecture to sustain a stream of data at these bandwidths to the processing elements. We review examples of computational tasks that require scalable input/output, that is, computations where the I/O bandwidth of a processing element must grow in proportion to its computational bandwidth. We present several classes of optoelectronic architectures that can support a high-bandwidth data firehose and mention applications in switching, FFT, sorting, matrix?vector processing, database search, and processor-to-memory interconnect.
5486748
Scaling internet routers using optics
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of their expensive long-haul links. In this paper we consider how optics can be used to scale capacity and reduce power in a router. We start with the promising load-balanced switch architecture proposed by C-S. Chang. This approach eliminates the scheduler, is scalable, and guarantees 100% throughput for a broad class of traffic. But several problems need to be solved to make this architecture practical: (1) Packets can be mis-sequenced, (2) Pathological periodic traffic patterns can make throughput arbitrarily small, (3) The architecture requires a rapidly configuring switch fabric, and (4) It does not work when linecards are missing or have failed. In this paper we solve each problem in turn, and describe new architectures that include our solutions. We motivate our work by designing a 100Tb/s packet-switched router arranged as 640 linecards, each operating at 160Gb/s. We describe two different implementations based on technology available within the next three years.
9952136
Using a distributed single address space operating system to support modern cluster computing
Recent 64-bit microprocessors have made a huge 18.4 quintillion byte address space potentially available to programs. This has led to the design of operating systems that provide a single virtual address space in which all code and data reside in and across all levels of storage and all nodes of a distributed system. These operating systems, called single address space operating systems (SASOSs), have characteristics that can be used to support modern cluster computing in a distributed system in ways that provide an improved program development environment and higher performance than is available from conventional operating systems. Sombrero, our SASOS design, makes use of its hardware support for object-grained protection, separate thread-related protection domains and implicit protection domain crossing to provide support for modern cluster computing which is not available in SASOSs built on stock processors. Its design, which provides direct system-level support for object-oriented programming, includes a number of features targeted specifically at modern cluster computing.
30462765
Encoding transition systems in sequent calculus
Intuitionistic and linear logics can be used to specify the operational semantics of transition systems in various ways. We consider here two encodings: one uses linear logic and maps states of the transition system into formulas, and the other uses intuitionistic logic and maps states into terms. In both cases, it is possible to relate transition paths to proofs in sequent calculus. In neither encoding, however, does it seem possible to capture properties, such as simulation and bisimulation, that need to consider all possible transitions or all possible computation paths. We consider augmenting both intuitionistic and linear logics with a proof theoretical treatment of definitions. In both cases, this addition allows proving various judgments concerning simulation and bisimulation (especially for noetherian transition systems). We also explore the use of infinite proofs to reason about infinite sequences of transitions. Finally, combining definitions and induction into sequent calculus proofs makes it possible to reason more richly about properties of transition systems completely within the formal setting of sequent calculus.
5180180
Logic programming in a fragment of intuitionistic linear logic
The intuitionistic notion of context is refined by using a fragment of J.-Y. Girard's (Theor. Comput. Sci., vol.50, p.1-102, 1987) linear logic that includes additive and multiplicative conjunction, linear implication, universal quantification, the of course exponential, and the constants for the empty context and for the erasing contexts. It is shown that the logic has a goal-directed interpretation. It is also shown that the nondeterminism that results from the need to split contexts in order to prove a multiplicative conjunction can be handled by viewing proof search as a process that takes a context, consumes part of it, and returns the rest (to be consumed elsewhere). Examples taken from theorem proving, natural language parsing, and database programming are presented: each example requires a linear, rather than intuitionistic, notion of context to be modeled adequately.<<ETX>>
206447917
Creating Autonomous Roboticists
KISS Institute's Botball program is a national program, designed for middle and high school students, that uses the activities of robot building and programming to engage students in science, technology, engineering and mathematics. Botball puts robotics equipment into schools, then trains students and teachers in that equipment's use. The program is organized into spring regional tournaments and a national Botball tournament held at the Annual National Conference on Artificial Intelligence. This program is playing an important role in creating and inspiring the next generation of AI and robotics technologists, many of whom might very well be the engineers and computer scientists who design and build sophisticated, highly autonomous rovers and other space platforms for future NASA missions of exploration. The inspiration cuts both ways.
657782
Experiences with an Architecture for Intelligent, Reactive Agents
This paper briefly describes a robot architecture that has been under development for the last eight years. This architecture uses several levels of abstraction and description languages that are compatible between levels. The makeup of the architecture helps to coordinate planful activities with real-time behaviors for dealing with dynamic environments. In recent years, many architectures have been created with similar attributes. The two features that distinguish this architecture from most of those are: 1) a variety of useful software tools have been created to help implement this architecture on multiple real robots; and 2) this architecture, or parts of it have been implemented on over half a dozen very different robot systems using a variety of processors, operating systems, effectors and sensor suites.