Code-review, the systematic examination of source code, is widely used in industry, but seldom used in courses. We designed and implemented a rubric-driven online peer code-review system (PCR) that we have deployed for two semesters, during which 228 students performed over 1003 code reviews. PCR is designed to meet four goals: (1) Provide timely feedback to students on their submissions, (2) Teach students the art of code review, (3) Allow custom feedback on submissions even in massive online classes, and (4) Allow students to learn from each other. We report on using PCR, in particular, the accuracy of student-based reviews, the surprising number of free-form comments made by students, the variability of staff-based reviews, how student engagement impacts the accuracy, the additional workload, and anecdotal perspectives of students. We describe some critical design considerations for PCR including rubric design, the importance of PCR training on each assignment to acclimate students to the rubric, and how we match student reviewers to student submissions.

Understanding the relationship between a student's broader work habits and their performance, particularly on open-ended programming assignments, is key towards being able to guide students towards success. In spite of this, most evidence of student behavior and its relationship to performance is anecdotal. The advent of large-scale courses which use online tools for delivering course content, monitoring the programming environment, and providing automatic feedback as well as grading now makes it possible to dive into the data and develop data-driven methods for understanding how a student's approach to an assignment---from their first exposure to the description of the problem to their final submission of their completed assignment---influences their final performance.

Among the diversity of the existing modular robotic systems, we consider in this paper the subset of distributed modular robotic ensembles composed of resource-constrained identical modules that are organized in a lattice structure and which can only communicate with neighboring modules. These modular robotic ensembles form asynchronous distributed embedded systems. In many algorithms dedicated to distributed system coordination, a specific role has to be played by a leader, i.e., a single node in the system. This leader can be elected using various criteria. A possible strategy is to elect a center node, i.e., a node that has the minimum distance to all the other nodes. Indeed, this node is ideally located to communicate with all the others and this leads to better performance in many algorithms. The contribution of this paper is to propose the k-BFS SumSweep algorithm designed to elect an approximate-center node. We evaluated our algorithm both on hardware modular robots and in a simulator for large ensembles of robots. Experimental results show that k-BFS SumSweep is often the most accurate approximation algorithm (with an average relative accuracy between 90% to 100%) while using the fewest messages in large-scale systems, requiring only a modest amount of memory per node, and converging in a reasonable length of time.

Many distributed algorithms require a specific role to be played by a leader, a single node in the system. The choice of this node often has a direct impact on the performance. In particular, selecting a central node as the leader can significantly improve algorithm efficiency. Classical distributed algorithms require global information about the connectivity network to elect a centroid node. Thus, they are not suitable for large-scale distributed embedded systems with scarce computation, memory and energy resources. We present E2ACE, an Effective and Efficient Approximate-Centroid Election algorithm that uses O(1) memory space per node, O(d) time and O(mn^2) messages of size O(1), where n is the number of nodes, m the number of connections and d the diameter of the system. We evaluate our algorithm on the Blinky Blocks system using simulations. Experimental results show that E2ACE scales well in terms of accuracy, execution time and number of messages. We show that E2ACE is more accurate than the only existing algorithm with similar complexity results.

Modular self-reconfigurable robots are composed of independent connected modules which can self-rearrange their connectivity using processing, communication and motion capabilities, in order to change the overall robot structure. In this paper, we consider rolling cylindrical modules arranged in a two-dimensional vertical hexagonal lattice. We propose a parallel, asynchronous and fully decentralized distributed algorithm to self-reconfigure robots from an initial configuration to a goal one. We evaluate our algorithm on the millimeter-scale cylindrical robots, developed in the Claytronics project, through simulation of large ensembles composed of up to ten thousand modules. We show the effectiveness of our algorithm and study its performance in terms of communications, movements and execution time. Our observations indicate that the number of communications, the number of movements and the execution time of our algorithm is highly predictable. Furthermore, we observe execution times that are linear in the size of the goal shape.

In this paper, we propose the Modular Robot Time Protocol (MRTP), a network-wide time synchronization protocol for modular robots. Our protocol achieves its performance by combining several mechanisms: central time master election, low-level time-stamping and clock skew compensation using linear regression. We evaluate our protocol on the Blinky Blocks hardware. Experimental results show that MRTP can potentially manage real systems composed of up to 27,775 Blinky Blocks. We observe that the synchronization precision depends on the hardware, the hop distance to the time master, the synchronization periods and the number of synchronization points used for the linear regressions. Furthermore, we show that our protocol is able to keep a Blinky Blocks system synchronized to a few milliseconds, using few network resources at runtime, even-though the Blinky Blocks hardware clocks exhibit very poor accuracy and resolution.

Declarative programming has been hailed as a promising approach to parallel programming since it makes it easier to reason about programs while hiding the implementation details of parallelism from the programmer. However, its advantage is also its disadvantage as it leaves the programmer with no straightforward way to optimize programs for performance. In this paper, we introduce Coordinated Linear Meld (CLM), a concurrent forward-chaining linear logic programming language, with a declarative way to coordinate the execution of parallel programs allowing the programmer to specify arbitrary scheduling and data partitioning policies. Our approach allows the programmer to write graph-based declarative programs and then optionally to use coordination to fine-tune parallel performance. In this paper we specify the set of coordination facts, discuss their implementation in a parallel virtual machine, and show---through example---how they can be used to optimize parallel execution. We compare the performance of CLM programs against the original uncoordinated Linear Meld and several other frameworks.

Modular robots are composed of many independent connected modules which are able to achieve common goals through communications. Many distributed algorithms have better performance if the modules that have to communicate with all the others, are placed at the center of the system. In this paper, we propose ABC-Center, an iterative algorithm for electing an approximate-center module in modular robots. ABC-Center uses O(1) space per module and O(kd) time, where k is the number of iterations required to terminate and d the diameter of the system. We evaluated our algorithm both on hardware modular robots and in a simulator for large ensemble of robots. The average expected eccentricity of the module elected by ABC-Center is less than 1.25 blocks off for random systems composed of up to 1000 modules. Furthermore, experiments show that our algorithm terminates after a few iterations. Hence, ABC-Center is scalable and adapted to modular robots with low memory resources.

Linear Meld is a concurrent forward-chaining linear logic programming language where logical facts can be asserted and retracted in a structured way. In Linear Meld, a program is seen as a database of logical facts and a set of derivation rules. The database of facts is partitioned by the nodes of a graph structure which leads to parallelism when nodes are executed simultaneously. Due to the foundations on linear logic, rules can retract facts in a declarative and structured fashion, leading to more expressive programs. We present the design and implementation of the virtual machine that we implemented to run Linear Meld on multicores, with particular focus on thread management, code organization, fact indexing, rule execution, and database organization for efficient fact insertion, lookup and deletion. Our results show that the virtual machine is capable of scaling programs with up to 16 threads and also exhibits interesting scalar performance results due to our indexing optimizations.

Abstract We have designed a new logic programming language called LM (Linear Meld) for programming graph-based algorithms in a declarative fashion. Our language is based on linear logic, an expressive logical system where logical facts can be consumed. Because LM integrates both classical and linear logic, LM tends to be more expressive than other logic programming languages. LM programs are naturally concurrent because facts are partitioned by nodes of a graph data structure. Computation is performed at the node level while communication happens between connected nodes. In this paper, we present the syntax and operational semantics of our language and illustrate its use through a number of examples.

In this paper we present an energy efficient control and power conversion circuit in a 1 μm HV SOI CMOS for a sub-millimeter robot known as a catom. The circuit provides power delivery through capacitive coupling and generates an internal high voltage that is then used to charge electrostatic actuation electrodes that move the robot. The architecture is implemented in a low power digital design and a novel high voltage driver that minimizes static power consumption for charging high voltage actuation electrodes. High voltage operation is extended by removing inherent parasitic FET gates through the post-processing removal of the Si backside carrier substrate of the SOI die.

In this article, we formalize locally distributed predicates , a concept previously introduced to address specific challenges associated with modular robotics and distributed debugging. A locally distributed predicate (LDP) is a novel construction for representing and detecting distributed properties in sparse-topology systems. Our previous work on LDPs presented empirical validation; here we show a formal model for two variants of the LDP algorithm, LDP-Basic and LDP-Snapshot, and establish performance bounds for these variants. We prove that LDP-Basic can detect strong stable predicates, that LDP-Snapshot can detect all stable predicates, and discuss their applicability to various distributed programming domains and to spatial computing in general. LDP detection in bounded-degree networks is shown to be scale-free, making the approach particularly attractive for specific topologies, even though LDPs are less efficient than snapshot algorithms in general distributed systems.

LDP (Locally Distributed Predicates) is a distributed, high-level language for programming modular reconfigurable robot systems (MRRs). In this paper we present the implementation of two motion-planning algorithms in LDP, and analyze both their performance and ease of implementation. We present multiple variations of one planner, including a novel resource allocation algorithm. We then draw conclusions about both the utility of the motion-planning algorithms and the suitability of LDP to the problem space. Our experiments suggest that metamodule-based planning approaches have a cost in time and/or energy terms, but that the cost can be worth paying in exchange for the additional generality and separation-of-concerns offered by these techniques. The particular tradeoff for a given system will depend upon its goals and the details of the underlying modules.

As the size of the modules in a self-reconfiguring modular robotic system shrinks and the number of modules increases, the flexibility of the system as a whole increases. In this paper, we describe the manufacturing methods and mechanisms for a 1 millimeter diameter module which can be manufactured en masse. The module is the first step towards realizing the basic unit of claytronics, a modular robotic system designed to scale to millions of units.

The prismatic cube style of modular robot is a promising design for realizing self-reconfigurable 3D lattices. Cubic lattices with prismatic transitions simplify many aspects of the hardware and planning control needed for reconfiguration. Despite much research on how cubic modules can coordinate to reconfigure, until now these transitions have not been fully demonstrated in hardware.We describe our movement primitives for both orthogonal and convex corner transitions with prismatic cube modules. We discuss the design of a hardware module capable of performing these transitions, as well as assess the performance of this hardware in an initial demonstration of these transitions.

Instruction selection is a key component of code generation. High quality instruction selection is of particular importance in the embedded space where complex instruction sets are common and code size is a prime concern. Although instruction selection on tree expressions is a well understood and easily solved problem, instruction selection on directed acyclic graphs is NP-complete. In this paper we present NOLTIS, a near-optimal, linear time instruction selection algorithm for DAG expressions. NOLTIS is easy to implement, fast, and effective with a demonstrated average code size improvement of 5.1% compared to the traditional tree decomposition and tiling approach.

We present a high-level language for programming modular robotic systems, based on locally distributed predicates (LDP), which are distributed conditions that hold for a connected subensemble of the robotic system. An LDP program is a collection of LDPs with associated actions which are triggered on any subensemble that matches the predicate. The result is a reactive programming language which efficiently and concisely supports ensemble-level programming. We demonstrate the utility of LDP by implementing three common, but diverse, modular robotic tasks.

In this paper we develop a theory of metamodules and an associated distributed asynchronous planner which generalizes previous work on metamodules for lattice-based modular robotic systems. All extant modular robotic systems have some form of non-holonomic motion constraints. This has prompted many researchers to look to metamodules, i.e., groups of modules that act as a unit, as a way to reduce motion constraints and the complexity of planning. However, previous metamodule designs have been specific to a particular modular robot. By analyzing the constraints found in modular robotic systems we develop a holonomic metamodule which has two important properties: (1) it can be used as the basic unit of an efficient planner and (2) it can be instantiated by a wide variety of different underlying modular robots, e.g., modular robot arms, expanding cubes, hex-packed spheres, etc. Using a series of transformations we show that our practical metamodule system has a provably complete planner. Finally, our approach allows the task of shape transformation to be separated into a planning task and a resource allocation task. We implement our planner for two different metamodule systems and show that the time to completion scales linearly with the diameter of the ensemble.

Asynchronous circuits are increasingly attractive as low power or high-performance replacements to synchronous designs. A key part of these circuits are asynchronous micropipelines; unfortunatelly, the existing micropipeline styles either improve performance or decrease power consumption, but not both. Very often, the pipeline register plays a crucial role in these cost metrics. In this paper we introduce a new register design, called self-resetting latches, for asynchronous micropipelines which bridges the gap between fast, but power hungry, latch-based designs and slow, but low power, flip-flop designs. The energy-delay metric for large asynchronous systems implemented with self-resetting latches is, on average, 41% better than latch-based designs and 15% better than flip-flop designs.

An effective method for focusing optimization effort on the most important parts of a design is to examine those elements on the critical path. Traditionally, the critical path is defined at the RTL level, as the longest path in the combinational logic between clocked registers. In this paper, we present a system-level timing analysis technique to define the concept of a global critical path (GCP), for predicting system-level performance. We show how the GCP can be used as a theoretical and practical tool for understanding, summarizing and optimizing the behavior of highly concurrent self-timed circuits. We formally define the GCP and show how it can be constructed using a discrete event model and hardware profiling techniques. The GCP provides valuable insight into the control-path behavior of circuits and in finding system-level bottlenecks. We have incorporated the GCP construction and analysis framework into a high-level synthesis and simulation toolchain, thus enabling complete automation in modeling, analysis and optimization.

Spatial Computing (SC) offers the potential for large improvements in performance and energy efficiency. Many proposed architectures have harnessed these benefits for small kernels. The Tartan architecture attempts to harness these advantages for entire general-purpose applications executing spatially. Previous work on Tartan had a configure-once model of execution, which required prohibitively large amounts of hardware resources to execute most programs. In this paper, we explore a virtualization model for Tartan. With virtualization, Tartan can execute large programs with a realistic amount of hardware, and with performance comparable to the configure-once model. We focus on three aspects of virtualization: runtime placement of code-blocks, location resolution methods for inter-block communication, and the impact of prefetching on reducing configuration delays. Our results show that the Tartan fabric can be virtualized with no loss in performance compared to a configure-once fabric of unlimited size.

We define operation chaining (op-chaining) as an optimiza- tion problem to determine the optimal pipeline depth for balancing performance against energy demands in pipelined asynchronous designs. Since there are no clock period requirements, asynchronous pipeline stages can have non-uniform latencies. We exploit this fact to coalesce several stages together thereby saving power and area due to the elimination of control-path resources from the pipeline. The trade-off is potentially reduced pipeline parallelism. In this paper, we formally define this optimization as a graph covering problem, which finds sub-graphs that will be synthesized as an op- chained pipeline stage. We then define the solution space for provably correct solutions and present an algorithm to efficiently search this space. The search technique partitions the graph based on post-dominator relationships to find sub-graphs that are potential op-chain candidates. We use knowledge of the Global Critical Path (GCP) [13] to evaluate the performance impact of accepting a candidate sub-graph and formulate a heuristic cost function to model this trade-off. The algorithm has a quadratic-time complexity in the size of the dataflow graph. We have implemented this algorithm within an automated asynchronous synthesis toolchain [12]. Experimental evidence from applying the algorithm on several media processing kernels reveals that the average energy- delay and energy-delay-area products improve by about 1.4x and 1.8x respectively, with a maximum improvement of 5x and 18x.

Tightly-coupled multi-agent systems such as modular robots frequently exhibit properties of interest that span multiple modules. These properties cannot easily be detected from any single module, though they might readily be detected by combining the knowledge of multiple modules. Testing for distributed conditions is especially important in debugging or verifying the correctness of software for modular robots. We have developed a technique we call distributed watchpoint triggers which can efficiently recognize such distributed conditions. Our watchpoint description language can handle a variety of temporal, spatial, and logical properties spanning multiple robots. This paper presents that language, describes our fully-distributed, online mechanism for detecting distributed conditions in a running system, and evaluates the performance of our implementation. We found that the performance of the system is highly dependent on the program being debugged, scales linearly with ensemble size, and is small enough to make the system practical in all but the worst case scenarios

This paper presents Meld, a programming language for modular robots, i.e., for independently executing robots where inter-robot communication is limited to immediate neighbors. Meld is a declarative language, based on P2, a logicprogramming language originally designed for programming overlay networks. By using logic programming, the code for an ensemble of robots can be written from a global perspective, as opposed to a large collection of independent robot views. This greatly simplifies the thought process needed for programming large ensembles. Initial experience shows that this also leads to a considerable reduction in code size and complexity. An initial implementation of Meld has been completed and has been used to demonstrate its effectiveness in the Claytronics simulator. Early results indicate that Meld programs are considerably more concise (more than 20× shorter) than programs written in C++, while running nearly as efficiently.

A simple and robust inter-module latch is possibly the most important component of a modular robotic system. This paper describes a latch based on electric fields and capacitive coupling. Our design provides not only significant adhesion forces, but can also be used for inter-module power transmission and communication. The key insight presented in this paper, and the factor that enables electrostatic adhesion to be effective at the macroscale, is the use of electric field attraction to generate frictional shear forces rather than electric field attraction alone. A second important insight is that a specific degree of flexibility in the electrodes is essential to maximize their mutual coupling and the resulting forces - electrodes which are too flexible or too rigid will perform less well. To evaluate the effectiveness of our latch we incorporate it into a cubic module 28 cm on a side. The result is a latch which requires almost zero static power and yet can hold 0.6 N/cm2of latch area.

One of the primary impediments to building ensembles of modular robots is the complexity and number of mechanical mechanisms used to construct the individual modules. As part of the Claytronics project - which aims to build very large ensembles of modular robots - we investigate how to simplify each module by eliminating moving parts and reducing the number of mechanical mechanisms on each robot by using force-at-a-distance actuators. Additionally, we are also investigating the feasibility of using these unary actuators to improve docking performance, implement intermodule adhesion, power transfer, communication, and sensing. In this paper we describe our most recent results in the magnetic domain, including our first design sufficiently robust to operate reliably in groups greater than two modules. Our work should be seen as an extension of systems such as Fracta [9], and a contrasting line of inquiry to several other researchers' prior efforts that have used magnetic latching to attach modules to one another but relied upon a powered hinge [10] or telescoping mechanism [12] within each module to facilitate self-reconfiguration.

Distributed reconfiguration is an important problem in multi-robot systems such as mobile sensor nets and metamorphic robot systems. In this work, we present a scalable distributed reconfiguration algorithm, hierarchical median decomposition, to achieve arbitrary target configurations. Our algorithm is built on top of a novel distributed median consensus estimator. The algorithms presented are fully distributed and do not require global communication. We show results from simulations in an open source multi-robot simulator.

Spatial Computing (SC) has been shown to be an energy-efficient model for implementing program kernels. In this paper we explore the feasibility of using SC for more than small kernels. To this end, we evaluate the performance and energy efficiency of entire applications on Tartan, a general-purpose architecture which integrates a reconfigurable fabric (RF) with a superscalar core. Our compiler automatically partitions and compiles an application into an instruction stream for the core and a configuration for the RF. We use a detailed simulator to capture both timing and energy numbers for all parts of the system.Our results indicate that a hierarchical RF architecture, designed around a scalable interconnect, is instrumental in harnessing the benefits of spatial computation. The interconnect uses static configuration and routing at the lower levels and a packet-switched, dynamically-routed network at the top level. Tartan is most energyefficient when almost all of the application is mapped to the RF, indicating the need for the RF to support most general-purpose programming constructs. Our initial investigation reveals that such a system can provide, on average, an order of magnitude improvement in energy-delay compared to an aggressive superscalar core on single-threaded workloads.

Stalls, due to mis-matches in communication rates, are a major performance obstacle in pipelined circuits. If the rate of data production is faster than the rate of consumption, the resulting design performs slower than when the communication rate is matched. This can be remedied by inserting pipeline buffers (to temporarily hold data), allowing the producer to proceed if the consumer is not ready to accept data. The problem of deciding which channels need these buffers (and how many) for an arbitrary communication profile is called the slack matching problem; the optimal solution to this problem has been shown to be NP-complete.

We describe a novel shape formation algorithm for ensembles of 2-dimensional lattice-arrayed modular robots, based on the manipulation of regularly shaped voids within the lattice ("holes"). The algorithm is massively parallel and fully distributed. Constructing a goal shape requires time proportional only to the complexity of the desired target geometry. Construction of the shape by the modules requires no global communication nor broadcast floods after distribution of the target shape. Results in simulation show 97.3% shape compliance in ensembles of approximately 60,000 modules, and we believe that the algorithm will generalize to 3D and scale to handle millions of modules

Motion planning for a self-reconfigurable robot involves coordinating the movement and connectivity of each of its homogeneous modules. Reconfiguration occurs when the shape of the robot changes from some initial configuration to a target configuration. Finding an optimal solution to reconfiguration problems involves searching the space of possible robot configurations. As this space grows exponentially with the number of modules, optimal planning becomes intractable. We propose a hierarchical planning approach that computes heuristic global reconfiguration strategies efficiently. Our approach consists of a base planner that computes an optimal solution for a few modules and a hierarchical planner that calls this base planner or reuses pre-computed plans at each level of the hierarchy to ultimately compute a global suboptimal solution. We present results from a prototype implementation of the method that efficiently plans for self-reconfigurable robots with several thousand modules. We also discuss tradeoffs and performance issues including scalability, heuristics and plan optimality

This paper describes a global progressive register allocator, a register allocator that uses an expressive model of the register allocation problem to quickly find a good allocation and then progressively find better allocations until a provably optimal solution is found or a preset time limit is reached. The key contributions of this paper are an expressive model of global register allocation based on multicommodity network flows that explicitly represents spill code optimization, register preferences, copy insertion, and constant rematerialization; two fast, but effective, heuristic allocators based on this model; and a more elaborate progressive allocator that uses Lagrangian relaxation to compute the optimality of its allocations. Our progressive allocator demonstrates code size improvements as large as 16.75% compared to a traditional graph allocator. On average, we observe an initial improvement of 3.47%, which increases progressively to 6.84% as more time is permitted for compilation.

A major obstacle to successful high-level synthesis (HLS) of large-scale application-specified integrated circuit systems is the presence of memory accesses to a shared-memory subsystem. The latency to access memory is often not statically predictable, which creates problems for scheduling operations dependent on memory reads. More fundamental is that dependences between accesses may not be statically provable (e.g., if the specification language permits pointers), which introduces memory-consistency problems. Addressing these issues with static scheduling results in overly conservative circuits, and thus, most state-of-the-art HLS tools limit memory systems to those that have predictable latencies and limit programmers to specifications that forbid arbitrary memory-reference patterns. A new HLS framework for the synthesis and optimization of memory accesses (SOMA) is presented. SOMA enables specifications to include arbitrary memory references (e.g., pointers) and allows the memory system to incorporate features that might cause the latency of a memory access to vary dynamically. This results in raising the level of abstraction in the input specification, enabling faster design times. SOMA synthesizes a memory access network (MAN) architecture that facilitates dynamic scheduling and ordering of memory accesses. The paper describes a basic MAN construction technique that illustrates how dynamic ordering helps in efficiently maintaining memory consistency and how dynamic scheduling helps alleviate the variable-latency problem. Then, it is shown how static analysis of the access patterns can be used to optimize the MAN. One optimization changes the MAN interconnect topology to increase concurrence. A second optimization reduces the synchronization overhead necessary to maintain memory consistency. Postlayout experiments demonstrate that SOMA's application-specific MAN construction significantly improves power and performance for a range of benchmarks.

Register allocation is one of the most important optimizations a compiler performs. Conventional graph-coloring based register allocators are fast and do well on regular, RISC-like, architectures, but perform poorly on irregular, CISC-like, architectures with few registers and non-orthogonal instruction sets. At the other extreme, optimal register allocators based on integer linear programming are capable of fully modeling and exploiting the peculiarities of irregular architectures but do not scale well. We introduce the idea of a progressive allocator. A progressive allocator finds an initial allocation of quality comparable to a conventional allocator, but as more time is allowed for computation the quality of the allocation approaches optimal. This paper presents a progressive register allocator which uses a multi-commodity network flow model to elegantly represent the intricacies of irregular architectures. We evaluate our allocator as a substitute for gcc 's local register allocation pass.

Nanoscale technologies provide both challenges and opportunities. We show that the issues and potential solutions facing designers are technology independent and arise mainly from shrinking device sizes and an increase in the number of devices available. We explore how it is possible to use some of the devices that will be available to help ease design complexity as well as overcome process related challenges such as limited layout freedom, increased defect densities, timing constraints, and power dissipation.

This paper describes a novel approach to powering a radical type of microrobot. Our long-term aim is to enable the construction of ensembles of millions of coordinated near-spherical, submillimeter microrobots. Both the large number of potential simultaneous neighbors of each robot (12) and the difficulty of fine actuation at such small scales preclude the use of complex connectors previously developed in many modular robotics efforts. Instead, we propose to leverage multirobot cooperation to simplify the mechanics of modular robot docking. In our approach, the robots actively cooperate to route virtual power busses (both supply and ground) to all the robots in the ensemble using only unary (single conductor) electrical connectors between robots. A unary connector allows for larger tolerances in engagement angle, simplifies robot manufacture, speeds reconfiguration, and maximizes the proportion of the connector surface area useful for carrying current. The algorithms we present permit a robot ensemble to efficiently harvest and distribute power from sources discovered in the environment and/or carried by the ensemble. We evaluate these algorithms in a variety of simulated deployment conditions and report on the impact of hardware defects, limited on-board power storage, and the ensemble-environment interface.

There has been a resurgence of interest in dataflow architectures, because of their potential for exploiting parallelism with low overhead. In this paper we analyze the performance of a class of static dataflow machines on integer media and control-intensive programs and we explain why a dataflow machine, even with unlimited resources, does not always outperform a superscalar processor on general-purpose codes, under the assumption that both machines take the same time to execute basic operations. We compare a program-specific dataflow machine with unlimited parallelism to a superscalar processor running the same program. While the dataflow machines provide very good performance on most data-parallel programs, we show that the dataflow machine cannot always take advantage of the available parallelism. Using the dynamic critical path we investigate the mechanisms used by superscalar processors to provide a performance advantage and their impact on a dataflow model

We propose a demonstration of extremely scalable modular robotics algorithms developed as part of the Claytronics Project (http://www-2.cs.cmu.edu/~claytronics/), as well as a demonstration of proof-of-concept prototypes. Our effort envisions multi-million-module robot ensembles able to morph into three-dimensional scenes, eventually with sufficient fidelity so as to convince a human observer the scenes are real. Although this work is potentially revolutionary in the sense that it holds out the possibility of radically altering the relationship between computation, humans, and the physical world, many of the research questions involved are similar in flavor to more mainstream systems research, albeit larger in scale. For instance, as in sensor networks, each robot will incorporate sensing, computation, and communications components. However, unlike most sensor networks each robot will also include mechanisms for actuation and motion. Many of the key challenges in this project involve coordination and communication of sensing and actuation across such large ensembles of independent units.

This paper describes a computer architecture, Spatial Computation (SC), which is based on the translation of high-level language programs directly into hardware structures. SC program implementations are completely distributed, with no centralized control. SC circuits are optimized for wires at the expense of computation units.In this paper we investigate a particular implementation of SC: ASH (Application-Specific Hardware). Under the assumption that computation is cheaper than communication, ASH replicates computation units to simplify interconnect, building a system which uses very simple, completely dedicated communication channels. As a consequence, communication on the datapath never requires arbitration; the only arbitration required is for accessing memory. ASH relies on very simple hardware primitives, using no associative structures, no multiported register files, no scheduling logic, no broadcast, and no clocks. As a consequence, ASH hardware is fast and extremely power efficient.In this work we demonstrate three features of ASH: (1) that such architectures can be built by automatic compilation of C programs; (2) that distributed computation is in some respects fundamentally different from monolithic superscalar processors; and (3) that ASIC implementations of ASH use three orders of magnitude less energy compared to high-end superscalar processors, while being on average only 33% slower in performance (3.5x worst-case).

We examine the opportunities brought about by recent progress in electronic nanotechnology and describe the methods needed to harness them for building a new computer architecture. In this process we decompose some traditional abstractions, such as the transistor, into fine-grain pieces, such as signal restoration and input-output isolation. We also show how we can forgo the extreme reliability of CMOS circuits for low-cost chemical self-assembly at the expense of large manufacturing defect densities. We discuss advanced testing methods that can be used to recover perfect functionality from unreliable parts. We proceed to show how the molecular switch, the regularity of the circuits created by self-assembly and the high defect densities logically require the use of reconfigurable hardware as a basic building block for hardware design. We then capitalize on the convergence of compilation and hardware synthesis (which takes place when programming reconfigurable hardware) to propose the complete elimination of the instruction-set architecture from the system architecture, and the synthesis of asynchronous dataflow machines directly from high-level programming languages, such as C. We discuss in some detail a scalable compilation system that performs this task.

We present the internal representation and optimizations used by the CASH compiler for improving the memory parallelism of pointer-based programs. CASH uses an SSA-based representation for memory, which compactly summarizes both control-flow- and dependence information. In CASH, memory optimization is a four-step process: (1) first an initial, relatively coarse representation of memory dependences is built; (2) next, unnecessary memory dependences are removed using dependence tests; (3) third, redundant memory operations are removed (4) finally, parallelism is increased by pipelining memory accesses in loops. While the first three steps above are very general, the loop pipelining transformations are particularly applicable for spatial computation, which is the primary target of CASH. The redundant memory removal optimizations presented are: load/store hoisting (subsuming partial redundancy elimination and common-subexpression elimination), load-after-store removal, store-before-store removal (dead store removal) and loop-invariant load motion. One of our loop pipelining transformations is a new form of loop parallelization, called loop decoupling. This transformation separates independent memory accesses within a loop body into several independent loops, which are allowed dynamically to slip with respect to each other A new computational primitive, a token generator is used to dynamically control the amount of slip, allowing maximum freedom, while guaranteeing that no memory dependences are violated.

As the dominating CMOS technology is fast approaching a "brick wall," new opportunities arise for competing solutions. Nanoelectronics has achieved several breakthroughs lately and promises to overcome many of the limitations intrinsic to current semiconductor approaches. Most of the results in this area reported until now focus on devices and interconnect; this work goes several steps further and presents issues related to circuits and architecture. Based on proposed nanoscale interconnect and device structures, we explore the design space available to the nanoelectronic circuit designer and system architect.

In this paper we describe a peer-to-peer interface between processor cores and reconfigurable fabrics. The main advantage of the peer-to-peer model is that it greatly expands the scope of application for reconfigurable computing and hence its potential benefits. The primary extension in our model is that "code" on the reconfigurable hardware unit is allowed to invoke routines both on the reconfigurable unit itself and on the fixed logic processor We describe the software constructs and compilation mechanisms needed for such an architecture, including a detailed description of the interface between the two parts of the application.

As the size of reconfigurable fabrics increases we can envision entire applications being mapped to a reconfigurable device; not just the code, but also the memory. These larger circuits, unfortunately, will suffer from the problem of a growing memory bottleneck. In this paper we explore how mobile memory techniques, inspired by cache-only memory architectures, can be applied to help solve this problem. The basic idea is to move the memory to the location of the accessor. Using both an analytical model and simulation we investigate several different memory movement algorithms. The results show that mobility can, on average, decrease memory latency 2x; which translates into speedup of about 15%.

New electronics technologies are emerging which may carry us beyond the limits of lithographic processing down to molecular-scale feature sizes. Devices and interconnects can be made from a variety of molecules and materials including bistable and switchable organic molecules, carbon nanotubes, and, single-crystal semiconductor nanowires. They can be self-assembled into organized structures and attached onto lithographic substrates. This tutorial reviews emerging molecular-scale electronics technology for CAD and system designers and highlights where ICCAD research can help support this technology.

The continuation of the remarkable exponential increases in processing power over the recent past faces imminent challenges due in part to the physics of deep-submicron CMOS devices and the costs of both chip masks and future fabrication plants. A promising solution to these problems is offered by an alternative to CMOS-based computing, chemically assembled electronic nanotechnology (CAEN).In this paper we outline how CAEN-based computing can become a reality. We briefly describe recent work in CAEN and how CAEN will affect computer architecture. We show how the inherently reconfigurable nature of CAEN devices can be exploited to provide high-density chips with defect tolerance at significantly reduced manufacturing costs. We develop a layered abstract architecture for CAEN-based computing devices and we present preliminary results which indicate that such devices will be competitive with CMOS circuits.

Reconfigurable computing obtains its performance advantage over fixed processors by creating hardware configurations that are specialized for a particular application. In some cases, this advantage can be pushed even further, by creating hardware specialized to a particular instance of an application. For many problems where this approach is applicable, such as automatic target recognition, template matching and encryption, the problem parameters can change often, even within a single program execution, requiring periodic, and potentially expensive, hardware reconfigurations. To support these applications, we propose a method for on-chip configuration generation, or embedded compilation, for use with Carnegie Mellon University's PipeRench reconfigurable processor. We describe PipeRench's performance in detail for one problem, template matching, relative to the newest general-purpose processors, and show how embedded compilation can be used to support multiple problem instances for a second problem, IDEA encryption.

Fault tolerance is becoming an increasingly important issue, especially in mission-critical applications where data integrity is a paramount concern. Performance, however, remains a large driving force in the market place. Runtime reconfigurable hardware architectures have the power to balance fault tolerance with performance, allowing the amount of fault tolerance to be tuned at run-time. This paper describes a new built-in self-test designed to run on, and take advantage of, runtime reconfigurable architectures using the PipeRench architecture as a model. In addition, this paper introduces a new metric by which a user can set the desired fault tolerance of a runtime reconfigurable device.

Reconfigurable computing devices have achieved substantial performance improvements over conventional processors on some computational kernels. These benefits derive from hardware customization which avoids the mismatch between the basic requirements of the algorithms and the architectures of the processors. A reconfigurable fabric alone is not sufficient for general-purpose computing since it can be ill-suited to executing entire programs due to space limitations, dataflow-centricity, and inefficiency at implementing some operations (e.g. floating-point arithmetic). These observations have led to the appearance of numerous designs which place some form of reconfigurable logic under the control of a general-purpose processor. The authors explore the ways in which a reconfigurable fabric can be interfaced with a general-purpose processor. While off-chip reconfigurable fabrics have proven to be quite effective at performing streaming, data-intensive computations, they require large streams of data to overcome the latency between the devices. We explore the design space for an on-chip fabric, i.e., a reconfigurable function unit (RFU). An RFU allows smaller portions of application to be mapped to the fabric in the form of custom instructions. Though the speedups achieved for stream based computations will in general be much larger than those for custom instructions, they are limited to a smaller class of applications. Custom instructions, however, can be found in a larger class of programs, and compiler techniques can automatically create them.

In this paper, we present a fast and efficient compilation methodology for pipeline reconfigurable architectures. Our compiler back-end is much faster than conventional CAD tools, and fairly efficient. We represent pipeline reconfigurable architectures by a generalized VLIW-like model. The complex architectural constraints are effectively expressed in terms of a single graph parameter: the routing path length (RPL). Compiling to our model using RPL, we demonstrate fast compilation times and show speedups of between 10x and 200x on a pipeline reconfigurable architecture when compared to an UltraSparc-II.

In this paper we describe a Configuration PRofiling tool (CPR) and show how it can be used to aid compiler designers, FPGA architects and in the construction of macro-generator libraries. CPR uses subgraph matching to identify the parts of an application which are most important to achieve high performance. Using CPR as a guide we implemented a few macros for a macro-generator library, which yielded significant improvement in both the quality of configurations and speed of compilation.

In this paper we describe a compiler which quickly synthesizes high quality pipelined datapaths for pipelined reconfigurable devices. The compiler uses the same internal representation to perform synthesis, module generation, optimization, and place and route. The core of the compiler is a linear time place and route algorithm more than two orders of magnitude faster than traditional CAD tools. The key behind our approach is that we never backtrack, rip-up, or re-route. Instead, the graph representing the computation is preprocessed to guarantee routability by inserting lazy noops. The preprocessing steps provides enough information to make a greedy strategy feasible. The compilation speed is approximately 3000 bit-operations/second (on a PII/400Mhz) for a wide range of applications. The hardware utilization averages 60% on the target device, PipeRench. 1 Introduction Reconfigurable computing has the potential to change the way computing is performed. Such systems offer a many-fold in...

Future computing workloads will emphasize an architecture's ability to perform relatively simple calculations on massive quantities of mixed-width data. This paper describes a novel reconfigurable fabric architecture, PipeRench, optimized to accelerate these types of computations. PipeRench enables fast, robust compilers, supports forward compatibility, and virtualizes configurations, thus removing the fixed size constraint present in other fabrics. For the first time we explore how the bit-width of processing elements affects performance and show how the PipeRench architecture has been optimized to balance the needs of the compiler against the realities of silicon. Finally, we demonstrate extreme performance speedup on certain computing kernels (up to 190x versus a modern RISC processor), and analyze how this acceleration translates to application speedup.

The article defines a class of architectures for pipeline reconfigurable FPGAs by parameterizing a generic model. This class of architecture is sufficiently general to allow exploration of the most important design trade-offs. The parameters include the word size and LUT size, the number of global busses and registers associated with each logic block, and the horizontal interconnect within each stripe. We have developed an area model for the architecture that allows us to quickly estimate the area of an instance of the architectural class as a function of the parameter values. We compare the estimates generated by this model to one instance of the architecture that we have designed and fabricated.

While reconfigurable computing promises to deliver incomparable performance, it is still a marginal technology due to the high cost of developing and upgrading applications. Hardware virtualization can be used to significantly reduce both these costs. In this paper we describe the benefits of hardware virtualization, and show how it can be achieved using a combination of pipeline reconfiguration and run-time scheduling of both configuration streams and data streams. The result is PipeRench, an architecture that supports robust compilation and provides forward compatibility. Our preliminary performance analysis predicts that PipeRench will outperform commercial FPGAs and DSPs in both overall performance and in performance per mm2.

In this paper we present NIFDY, a network interface that uses admission control to reduce congestion and ensures that packets are received by a processor in the order in which they were sent, even if the underlying network delivers the packets out of order. The basic idea behind NIFDY is that each processor is allowed to have at most one outstanding packet to any other processor unless the destination processor has granted the sender the right to send multiple unacknowledged packets. Further, there is a low upper limit on the number of outstanding packets to all processors.We present results from simulations of a variety of networks (meshes, tori, butterflies, and fat trees) and traffic patterns to verify NIFDY's efficacy. Our simulations show that NIFDY increases throughput and decreases overhead. The utility of NIFDY increases as a network's bisection bandwidth decreases. When combined with the increased payload allowed by in-order delivery NIFDY increases total bandwidth delivered for all networks. The resources needed to implement NIFDY are small and constant with respect to network size.

In this paper we present substantially improved thread partitioning algorithms for modern implicitly parallel languages. We present a new block partitioning algorithm, separation constraint partitioning, which is both more powerful and more flexible than previous algorithms. Our algorithm is guaranteed to derive maximal threads. We present a theoretical framework for proving the correctness of our partitioning approach, and we show how separation constraint partitioning makes interprocedural partitioning viable.

This paper uses an abstract machine approach to compare the mechanisms of two parallel machines: the J-Machine and the CM-5. High-level parallel programs are translated by a single optimizing compiler to a fine-grained abstract parallel machine, TAM. A final compilation step is unique to each machine and optimizes for specifics of the architecture. By determining the cost of the primitives and weighting them by their dynamic frequency in parallel programs, we quantify the effectiveness of the following mechanisms individually and in combination. Efficient processor/network coupling proves valuable. Message dispatch is found to be less valuable without atomic operations that allow the scheduling levels to cooperate. Multiple hardware contexts are of small value when the contexts cooperate and the compiler can partition the register set. Tagged memory provides little gain. Finally, the performance of the overall system is strongly influenced by the performance of the memory system and the frequency of control operations.

No abstract available.

The design challenge for large-scale multiprocessors is (1) to minimize communication overhead, (2) allow communication to overlap computation, and (3) coordinate the two without sacrificing processor cost/performance. We show that existing message passing multiprocessors have unnecessarily high communication costs. Research prototypes of message driven machines demonstrate low communication overhead, but poor processor cost/performance. We introduce a simple communication mechanism, Active Messages, show that it is intrinsic to both architectures, allows cost effective use of the hardware, and offers tremendous flexibility. Implementations on nCUBE/2 and CM-5 are described and evaluated using a split-phase shared-memory extension to C, Split-C. We further show that active messages are sufficient to implement the dynamically scheduled languages for which message driven machines were designed. With this mechanism, latency tolerance becomes a programming/compiling concern. Hardware support for active messages is desirable and we outline a range of enhancements to mainstream processors.