The authors have been using Development Containers for a course in digital logic and computer organization for more than a year and have found that: 1) they make authentic experiences with the content accessible to all students, 2) they can virtually eliminate installation inconsistencies and the need for institutional support for software/hardware, and, most importantly, 3) they can be created and used in live, active-learning sessions in approximately 3 minutes!

Maintaining resources for courses in Digital Logic and Computer Architecture can be challenging at any scale or institution, especially if such courses are intended to provide authentic experience with contemporary tools, like Hardware Description Languages (HDLs) and Field Programmable Gate Arrays (FPGAs). A recent redesign of an introductory Digital Logic and Computer Architecture course at Washington University in St. Louis leveraged modern containerized environments, Codespaces and Development Containers, along with open-source tools to create a custom environment suited for hardware-focused courses in digital logic and computer architecture. This demo will introduce the system, which can easily be adopted by others. (Participants can create a full instance during the demonstration!) The environment is aligned with commonly used computer architecture texts and includes everything needed for a variety of assignments, including simulating designs (digital logic and assembly language) and deploying digital logic to low-cost FPGA platforms (

The development of FPGA-based applications using HLS is fraught with performance pitfalls and large design space exploration times. These issues are exacerbated when the application is complicated and its performance is dependent on the input dataset, as is often the case with graph neural network approaches to machine learning. Here, we introduce HLPerf, an open-source, simulation-based performance evaluation framework for dataflow architectures that both supports early exploration of the design space and shortens the performance evaluation cycle. We apply the methodology to GNNHLS, an HLS-based graph neural network benchmark containing six commonly used graph neural network models and four datasets with distinct topologies and scales. The results show that HLPerf achieves over 10, 000× average simulation acceleration relative to RTL simulation and over 400× acceleration relative to state-of-the-art cycle-accurate tools at the cost of 7% mean error rate relative to actual FPGA implementation performance. This acceleration positions HLPerf as a viable component in the design cycle.

FPGAs are widely deployed on high-energy astrophysics telescopes to preprocess and reduce sensor data read out by front-end electronics. Across instruments, these computational pipelines have similar semantics, sharing common stages such as pedestal subtraction, signal integration, zero-suppression, island detection, and centroiding. However, diverse telescope designs require unique implementations of these algorithms, and the logic is often rewritten from scratch for a new instrument.

The parallel execution of many graph algorithms is frequently dominated by data communication overheads between compute nodes. This bottleneck becomes even more pronounced in Near-Memory Processing (NMP) architectures with multiple memory cubes as local memory accesses are less expensive. Existing near-memory architectures typically use graph partitioning methods with a fixed vertex assignment, which limits their potential to improve performance and reduce energy consumption. Here, we argue that an NMP-based graph processing system should also consider the distribution of vertices onto memory cubes. We propose SuperCut, a framework for near-memory architectures to effectively reduce communication overheads while maintaining computational balance. We evaluate SuperCut via architectural simulation with 6 real-world datasets and 4 representative applications. The results show that it provides up to 1.8x total energy reduction and 2.6x speedup relative to current state-of-the-art approaches.

Tiny machine learning (TinyML) is an essential component of emerging smart microcontrollers (MCUs). However, the protection of the intellectual property (IP) of the model is an increasing concern due to the lack of desktop/server-grade resources on these power-constrained devices. In this paper, we propose STML, a system and algorithm co-design to Secure IP of TinyML on MCUs with ARM TrustZone. Our design jointly optimizes memory utilization and latency while ensuring the security and accuracy of emerging models. We implemented a prototype and benchmarked with 7 models, demonstrating STML reduces 40% of model protection runtime overhead on average.

We present GNNHLS, an open-source framework to comprehensively evaluate GNN inference acceleration on FPGAs via HLS, containing a software stack for data generation and baseline deployment and FPGA implementations of 6 well-tuned GNN HLS kernels. Evaluating on 4 graph datasets with distinct topologies and scales, the results show that GNNHLS achieves up to 50.8× speedup and 423× energy reduction relative to the CPU baselines. Compared with the GPU baselines, GNNHLS achieves up to 5.16× speedup and 74.5× energy reduction.

Many real-time systems run in dynamic environments where exogenous factors inform task workloads and deadlines, which may not be known prior to job release. A job of a task that would otherwise miss its deadline may adapt to remain schedulable by executing in a degraded state that reduces its workload. We suggest that such a task should adjust parameters of its computation over multiple dimensions to maintain schedulability while minimizing loss of utility, which we discuss for highly parallel fork-join tasks executing on a fixed number of dedicated processors. We identify the parameterized degrees of freedom over which workload can be adjusted, then characterize the impact of workload reduction on response time and utility. From this, we generate a Pareto-optimal surface over which efficient search, interpolation, and extrapolation enable online selection of task parameters at time of job release. We apply this approach to the Advanced Particle-astrophysics Telescope, a planned mission to perform real-time gamma-ray burst (GRB) localization using SWaP-constrained embedded hardware aboard an orbiting platform. Due to GRBs' dynamic and uncertain nature, the workload and deadline may not be known prior to job release. Nonetheless, even for bright GRBs that may otherwise take longer than a second to localize on candidate embedded hardware, our approach often enables sub-degree accuracy while meeting a 33 ms imposed deadline.

The promise of benefit from instrumentation on the farm is substantial. However, simply connecting existing equipment to the network is not sufficient to achieve these benefits, as the resulting system is vulnerable to a multitude of reliability and security issues. We describe an approach to instrumenting livestock barns, describing some of the innovations that enable cost-efficiency, which explicitly requires paying attention to the integration of new instrumentation with existing equipment. We then articulate a range of benefits that accrue, both to the livestock and to the farmer. The result is a comprehensive understanding of barn operations, yielding many of the benefits one aspires to with IoT on the farm.

This fun, hands-on workshop will show how to include significant computing concepts in engaging, creative activities that are accessible to students who have completed CS1. Participants will use Arduinos (provided) and experience a studio-style learning environment which can serve as an example for studio-based learning in the classroom. The maker movement is taking off, with accessible microcontrollers, sensors, actuators, and 3-D printing capability enabling do-it-yourself hobbyists of all ages to tinker in ways that previously were unavailable to the general public. At the heart of many maker projects is computer control, yet computer science education (especially in the early years) is primarily centered around traditional computing platforms: desktops, laptops, and servers, not the microcontrollers that are prevalent in the maker community. This workshop introduces curricular materials that can turn amateur makers into professional designers, understanding the underlying principles that drive the artifacts that makers make. The theoretical concepts covered include principles that are often present when computers interact with the physical world, e.g., timing as a functional requirement, physical inputs and outputs, etc. Finite automata are also introduced, in the form of finite-state machines, as an example of a computational formalism that has immediate practical use. The materials for a semester-long course (textbook, lecture videos, studios, assignments) are all freely available. The course expands upon the workshop subjects to also include the concepts of information representation, computer communications, and basic computer organization/architecture.

Domain specific computing is an idea that has been proposed as a path forward given the slowing of Moore’s Law and the breakdown of Dennard scaling [3]. Two fundamental questions include: (1) how does one define a domain; and (2) how does one go about architecting hardware that performs well for that domain? We present our preliminary work towards answering these questions.

The notion of IoT has taken the farm by storm. Irrigation is controlled to the resolution of individual plants, fertilizer is dispensed based on yields from previous growing cycles, and livestock feed, water, and environment are all monitored and under automatic control. Much of the equipment that performs this monitoring and control, however, predates the Internet of Things, and integrating this legacy equipment into modern communication systems is fraught with issues, particularly security issues. We describe our approach to providing secure, ubiquitous connectivity to a variety of previously isolated systems on the farm, enabling these systems to safely become part of the IoT.

Water treatment is one of those essential elements of modern life that is taken for granted by the general population. We describe the ability to remotely understand and improve water chemistry using IoT devices attached to the cloud. The commercial benefits of this IoT connectivity are substantial, including: reduced chemical usage, improved chemical inventory management, safer operation (fewer and less critical alarms), reduced maintenance costs, and higher quality water.

Embedded systems pervade nearly every aspect of modern life. Moreover, the emergence of both mobile platforms and Internet of Things (IoT) is furthering their reach. Although embedded systems are one of the bodies of knowledge in the ACM/IEEE-CS Com- puter Engineering Curricula, they have only passing mention in the ACM/IEEE-CS Computer Science Curricula. Inclusion of embedded systems concepts in undergraduate computer science can facilitate many objectives: a) they are an example of Platform-Based Devel- opment, a prominent theme in the ACM 2013 CS Curricula, b) they are often a more suitable level of complexity for educational needs than other "real world" platforms (e.g., Arduinos may be used to introduce many AP CS Principles in a single course), c) they offer a novel form of engagement, which may enhance diversity, and d) emerging areas, like IoT, are increasing demand for professionals that understand the full span of systems, from low-level firmware, to middleware and cloud computing. This panel represents three methods of including embedded systems concepts in undergraduate computer science: 1) use of em- bedded systems to improve engagement in a non-major computing course, 2) a required course covering core content for both com- puter science and computer engineering majors, and 3) a degree program offering a formal emphasis in embedded systems via a complementary set of courses. The panelists will share their motiva- tions for including embedded systems concepts in their programs, their approaches to integrating the content into their curricula, the teaching methods they use, the challenges they faced, and chal- lenges that remain.

The control of a catoptric (mirror-based) surface is decomposed hierarchically. The positioning control of individual mirrors is handled by low-level controllers for each drive motor, and the overall control decisions are guided by a Markov decision process.

Wireless communication is increasingly being used to federate embedded devices in a variety of distributed systems application domains, ranging from wireless sensor networks to the emerging "Internet of Things (IoT)." Since such embedded devices are tightly coupled both with their environments and with each other through their wireless communication channels, both variations in their environments and the system's need to respond (sometimes rapidly) to those variations may produce (1) the need for such devices to communicate and (2) with it the potential for channel contention to arise, dynamically at run-time. Thus, how wireless channels among the embedded devices are allocated and managed in these systems may significantly influence both communication-specific quality-of-service (QoS) properties (such as message throughput) and broader QoS properties (such as timeliness of system responsiveness) that depend on them. A growing body of research has focused on managing different aspects of wireless communication, but has done so mainly in an ad hoc manner, with respect to individual aspects rather than multiple aspects and their potential interactions. Even less attention has been paid to formal methods for assessing how combinations of aspects may influence communication performance, and how to characterize, adapt to, and exploit their combined effects, which is essential to address the challenges noted above. To overcome these limitations of the current state of the art, this paper makes three main contributions to wireless communication for distributed embedded systems with QoS constraints. First, it shows how a basic but fundamental set of channel admission and modulation decisions can be combined within a single Markov decision process (MDP) model to optimize (in expectation) objectives such as message throughput, even with stochastic arrival and interference characteristics. Second, it identifies regular structure in the value-optimal policies generated off-line from these models, which forms the basis for efficient and accurate heuristics suitable for on-line use. Third, it shows how single-and multi-variable regression techniques can be used to characterize key parameters that govern such regular structure, which then are used to instantiate those heuristics.

Because main memory is many times slower than modern processor cores, deep, multi-level cache hierarchies are ubiquitous in computers today. Similarly, applications deployed on ASICs and FPGAs are often hindered by slow external memories. Therefore, to achieve good performance, hardware designers must optimize main memory usage. Unfortunately, this process is often labor intensive and fails to explore the full range of potential memory designs. To address this issue for applications expressed in a streaming manner, we show that it is possible to generate automatically a superoptimized memory subsystem that can be deployed on an FPGA such that it performs better than a general-purpose memory subsystem. Rather than explore only simple memory subsystems, our superoptimizer is capable of exploring extremely complex designs consisting of multi-level caches and other components. Finally, we show that it is possible to deploy applications with superoptimized memory subsystems with minimal additional effort while achieving significant performance improvements over a naive memory subsystem.

Visualization of logic computations (i.e., by sharing a fixed function across distinct data streams) provides a means to effectively utilize hardware resources by context switching the logic to support multiple data streams of computation and to improve the total throughput of all streams. Context switching allows the pipeline stages of the logic to be fully utilized when feedback is present and to support additional contexts using secondary memory. In this paper, we analyze the performance of a virtualized hardware design and develop M/G/1 queueing model equations to predict circuit performance. The server is modeled using a general distribution that takes vacations during the computation of an individual data stream. Using the model, we predict circuit performance and tune a schedule for optimal performance.

When do you trust a model? More specifically, when can a model be used for a specific application? This question often takes years of experience and specialized knowledge to answer correctly. Once this knowledge is acquired it must be applied to each application. This involves instrumentation, data collection and finally interpretation. We propose the use of a trained Support Vector Machine (SVM) to give an automated system the ability to make an educated guess as to model applicability. We demonstrate a proof-of-concept which trains a SVM to correctly determine if a particular queueing model is suitable for a specific queue within a streaming system. The SVM is demonstrated using a micro-benchmark to simulate a wide variety of queueing conditions.

Virtualization of custom logic computations (i.e, by sharing a fixed function across distinct data streams) provides a means of computing multiple streams using shared hardware resources. The hardware can be context-switched to support virtualization using C-slow techniques (fine-grained context-switching) or by adding a secondary memory (coarse-grained context-switching). The performance of these computations depends on the circuit, technology, number of pipeline stages, number of streams, cost of a context switch, scheduling period, and arrival rate. In this paper, we analyze a virtualized hardware design and develop a set of analytic modeling equations for predicting the performance of these circuits. We then validate the model equations using a discrete-event simulation.

Highly-threaded many-core GPUs can provide high throughput for a wide range of algorithms and applications. Such machines hide memory latencies via the use of a large number of threads and large memory bandwidth. The achieved performance, therefore, depends on the parallelism exploited by the algorithm, the effectiveness of latency hiding, and the utilization of multiprocessors (occupancy). In this paper, we extend previously proposed analytical models, jointly addressing parallelism, latency-hiding, and occupancy. In particular, the model not only helps to explore and reduce the configuration space for tuning kernel execution on GPUs, but also reflects performance bottlenecks and predicts how the runtime will trend as the problem and other parameters scale. The model is validated with empirical experiments. In addition, the model points to at least one circumstance in which the occupancy decisions automatically made by the scheduler are clearly sub-optimal in terms of runtime.

Virtualization of custom logic computations (i.e., by sharing a fixed function across distinct data streams), provides a means of reusing limited hardware resources. This is common practice in traditional processors where more than one user can share processor resources. In this paper, we virtualize a custom logic block using C-slow techniques to support fine-grain context-switching. We then develop and present an analytic model for several performance measures (throughput, latency, input queue occupancy) for both fine- and coarse-grained context switching. Next, we calibrate the analytic performance model with empirical measurements. We then validate the model via discrete-event simulation and use the model to predict the performance and develop optimal schedules for virtualized logic computations.

Streaming computing is a paradigm of distributed computing that features networked nodes connected by first-in-first-out data channels. Communication between nodes may include not only high-volume data tokens but also infrequent and unpredictable control messages carrying control information, such as data set boundaries, exceptions, or reconfiguration requests. In many applications, it is necessary to order delivery of control messages precisely relative to data tokens, which can be especially challenging when nodes can filter data tokens. Existing approaches, mainly data serialization protocols, do not exploit the low-volume nature of control messages and may not guarantee that synchronization of these messages with data will be free of deadlock. In this paper, we propose an efficient messaging system for adding precisely ordered control messages to streaming applications. We use a credit-based protocol to avoid the need to tag data tokens and control messages. For potential deadlocks caused by filtering behavior and global synchronization, we propose deadlock avoidance solutions and prove their correctness.

The disparity in performance between processors and main memories has led computer architects to incorporate large cache hierarchies in modern computers. Because these cache hierarchies are designed to be general-purpose, they may not provide the best possible performance for a given application. In this paper, we determine a memory subsystem well suited for a given application and main memory by discovering a memory subsystem comprised of caches,scratchpads, and other components that are combined to provide better performance. We draw motivation from the superoptimization of instruction sequences, which successfully finds unusually clever instruction sequences for programs. Targeting both ASIC and FPGA devices, we show that it is possible to discover unusual memory subsystems that provide performance improvements over a typical memory subsystem.

The Threaded many-core memory (TMM) model provides a framework to analyze the performance of algorithms on GPUs. Here, we investigate the effectiveness of the TMM model by analyzing algorithms for 3 classic problems -- suffix tree/array for string matching, fast Fourier transform, and merge sort -- under this model. Our findings indicate that the TMM model can explain and predict previously unexplained trends and artifacts in experimental data.

A number of highly-threaded, many-core architectures hide memory-access latency by low-overhead context switching among a large number of threads. The speedup of a program on these machines depends on how well the latency is hidden. If the number of threads were infinite, theoretically, these machines could provide the performance predicted by the PRAM analysis of these programs. However, the number of threads per processor is not infinite, and is constrained by both hardware and algorithmic limits. In this paper, we introduce the Threaded Many-core Memory (TMM) model which is meant to capture the important characteristics of these highly-threaded, many-core machines. Since we model some important machine parameters of these machines, we expect analysis under this model to provide a more fine-grained and accurate performance prediction than the PRAM analysis. We analyze 4 algorithms for the classic all pairs shortest paths problem under this model. We find that even when two algorithms have the same PRAM performance, our model predicts different performance for some settings of machine parameters. For example, for dense graphs, the dynamic programming algorithm and Johnson’s algorithm have the same performance in the PRAM model. However, our model predicts different performance for large enough memory-access latency and validates the intuition that the dynamic programming algorithm performs better on these machines. We validate several predictions made by our model using empirical measurements on an instantiation of a highly-threaded, many-core machine, namely the NVIDIA GTX 480.

The streaming model is a popular model for writing high-throughput parallel applications. A streaming application is represented by a graph of computation stages that communicate with each other via FIFO channels. In this paper, we consider the problem of mapping streaming pipelines - streaming applications where the graph is a linear chain - onto a set of computing resources in order to maximize its throughput. In a parallel setting, subsets of stages, called components, can be mapped onto different computing resources. The throughput of an application is determined by the throughput of the slowest component. Therefore, if some stage is much slower than others, then it may be useful to replicate the stage's code and divide its workload among two or more replicas in order to increase throughput. However, pipelines may consist of some replicable and some non-replicable stages. In this paper, we address the problem of mapping these partially replicable streaming pipelines onto both homogeneous and heterogeneous platforms so as to maximize throughput. We consider two types of platforms, homogeneous platforms - where all resources are identical, and heterogeneous platforms - where resources may have different speeds. In both cases, we consider two network topologies-unidirectional chain and clique. We provide polynomial-time algorithms for mapping partially replicable pipelines onto unidirectional chains for both homogeneous and heterogeneous platforms. For homogeneous platforms, the algorithm for unidirectional chains generalizes to clique topologies. However, for heterogeneous platforms, mapping these pipelines onto clique topologies is NP-complete. We provide heuristics to generate solutions for cliques by applying our chain algorithms to a series of chains sampled from the clique. Our empirical results show that these heuristics rapidly converge to near-optimal solutions.

Modern hardware is often heterogeneous. With heterogeneity comes multiple abstraction layers that hide underlying complex systems. This complexity makes quantitative performance modeling a difficult task. Designers of high-performance streaming applications for heterogeneous systems must contend with unpredictable and often non-generalizable models to predict performance of a particular application and hardware mapping. This paper outlines a computationally simple approach that can be used to model the overall throughput and buffering needs of a streaming application on heterogeneous hardware. The model presented is based upon a hybrid maximum flow and decomposed discrete queueing model. The utility of the model is assessed using a set of real and synthetic benchmarks with model predictions compared to measured application performance.

Current state of the art systems contain various types of multicore processors, General Purpose Graphics Processing Units (GPGPUs) and occasionally Digital Signal Processors (DSPs) or Field-Programmable Gate Arrays (FPGAs). With heterogeneity comes multiple abstraction layers that hide underlying complexity. While necessary to ease programmability of these systems, this hidden complexity makes quantitative performance modeling a difficult task. This paper outlines a computationally simple approach to modeling the overall throughput and buffering needs of a streaming application deployed on heterogeneous hardware.

The stochastic nature of wireless communication suggests a Markov Decision Process (MDP) as a formalism for identifying and evaluating spectrum control policies. However, in practice numerous factors influence the success or failure of a transmission, so that the applicability of particular MDP models to real spectrum management problems must itself be examined. This paper presents a series of model validation studies in which correspondence between an MDP model and a discrete-event simulation (DES) model is evaluated. We test several hypotheses that together provide a foundation and an exemplar for the idea of using MDPs to guide management of shared spectrum. We conclude that there is sufficient similarity between the performance predictions made by the MDP model and the DES model that MDPs can be used effectively to determine spectrum control policies.

Streaming data programs are an important class of applications, for which queueing network models are frequently available. While the design space can be large, decomposition techniques can be effective at design space reduction. We introduce two decomposition techniques called convex decomposition and unchaining and present implications for a biosequence search application.

Graphics engines are excellent execution platforms for high-throughput computations that exploit a large degree of available parallelism. The achieved performance is, however, highly dependent on the access patterns that the applicationimposes on the memory subsystem. Here, we propose an analytic model that helps improve the understanding of the performance of memory-limited kernels that employ randommemory access schemes, especially as impacted by cache andvarious configuration parameters that can be used to tunekernel execution, such as the number of blocks and the number of threads per block. The analytic model is first explored through the use of a synthetic micro-benchmark, which is then followed by an empirical validation using a pair of production applications used in computational biology.

Summary form only given. ScalaPipe is a streaming application generator for heterogeneous platforms. By using a collection of domain-specific languages (DSLs) embedded in the Scala programming language, ScalaPipe allows creation of streaming applications that can run on a variety of hardware, including traditional processors, graphics processors, and field-programmable gate arrays (FPGAs). Its application DSL allows specification of the application topology and resource mapping. Its block DSL allows the authoring of implementations for processing kernels, or blocks, which are used in the streaming application. ScalaPipe makes it easy to generate, modify, and instrument large, complex topologies and resource mappings while also exposing optimization opportunities.

Many-core architectures are excellent in hiding memory-access latency by low-overhead context switching among a large number of threads. The speedup of algorithms carried out on these machines depends on how well the latency is hidden. If the number of threads were infinite, then theoretically these machines should provide the performance predicted by the PRAM analysis of the programs. However, the number of allowable threads per processor is not infinite. In this paper, we introduce the Threaded Many-core Memory (TMM) model which is meant to capture the important characteristics of these highly-threaded, many-core machines. Since we model some important machine parameters of these machines, we expect analysis under this model to give more fine-grained performance prediction than the PRAM analysis. We analyze 4 algorithms for the classic all pairs shortest paths problem under this model. We find that even when two algorithms have the same PRAM performance, our model predicts different performance for some settings of machine parameters. For example, for dense graphs, the Floyd-Warshall algorithm and Johnson's algorithms have the same performance in the PRAM model. However, our model predicts different performance for large enough memory-access latency and validates the intuition that the Floyd-Warshall algorithm performs better on these machines.

Streaming data applications are frequently pipelined and deployed on application-specific systems to meet performance requirements and resource constraints. Typically, there are several design parameters in the algorithms and architectures used that impact the application performance as well as resource utilization. Efficient exploration of this design space is the goal of this research. When using architecturally diverse systems to accelerate streaming applications, the design search space is often complex. The search complexity can be reduced by recognizing and exploiting convex variables to perform convex decomposition, preserving optimality even in the context of a non-convex optimization problem. This paper presents a formal treatment of convex variables and convex decomposition, including a proof that the technique preserves optimality. It also quantifies the reduction in the search space that is realized, at minimum equal to the number of distinct values of the convex variable and potentially much higher.

Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can deadlock. One method of deadlock avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to avoid deadlock.

Finding performance bottlenecks in application-specific systems is becoming increasingly labor-intensive as the capabilities of these systems improve. The complex platforms required to meet today's high application performance demands put pressure on developers to sustain current design cycles. Application developers need better tools to diagnose performance issues that arise when utilizing real-world application-specific platforms, from embedded applications to high-performance computational science applications. In this paper, we present TimeTrial, a runtime performance monitoring system that profiles streaming data applications deployed on architecturally diverse computers. TimeTrial is designed to operate with minimal impact on the executing application, exploiting user directives to aggressively perform lossy compression on performance meta-data. We present the design of the TimeTrial performance monitor and demonstrate its use in discovering performance bottlenecks in a production computational biology application.

Many embedded and scientific applications are pipelined (i.e., streaming) and deployed on application-specific systems. Typically, there are several design parameters in the algorithms and architectures used that impact the tradeoff between different metrics of application performance as well as resource utilization. Efficient automatic exploration of this design space is the goal of our research. We present a global optimization framework comprising a domain-specific variation of branch-and-bound that reduces search complexity by exploiting the topology of the application's pipelining. We exploit the topological information to discover decomposability through the canonical Jordan block form. The reduction in search complexity for four real-world streaming applications (drawn from the literature) is significant, ranging from a million-fold reduction in search space size to a reduction factor of 10 billion. All four optimization problems are thereby solvable in reasonable time.

Modern embedded systems are increasingly likely to be distributed across multiple devices and platforms that must interact with high precision across wireless networks. Traditional ways of managing the wireless radio spectrum suffer from two fundamental limitations, which the research presented in this paper addresses: (1) spectrum is divided a priori into static coarse-grained partitions without reference to details of particular applications, and (2) partitions are non-overlapping, which although beneficial to reduce interference prevents a much greater utilization of the spectrum through carefully allowing overlap of spectrum allocations. To overcome these limitations, we propose an approach to spectrum allocation based on dynamic allocation of diverse portions of the overall spectrum and overlapping allocations to increase utilization. This paper makes three main contributions to the state of the art in spectrum management for embedded systems: (1) it examines how memory management techniques such as Knuth's buddy algorithm can be applied to spectrum management, in the face of transmission failures that may arise from the physical environment, (2) it extends that approach to consider transmission failures resulting from interference, when overlapping regions of spectrum are allocated to increase utilization, and (3) it presents results of simulation experiments we conducted to evaluate those approaches, which demonstrate their efficacy and suggest future extensions based on them.

Time Trial is a low-impact performance monitor that supports streaming data applications deployed on a variety of architecturally diverse computational platforms, including multicore processors and field-programmable gate arrays. Communication between resources in architecturally diverse systems is frequently a limitation to overall application performance. Understanding these bottlenecks is crucial to understanding overall application performance. Direct measurement of inter-resource communications channel occupancy is not readily achievable without significantly impacting performance of the application itself. Here, we present Time Trial's approach to monitoring those queues that cross platform boundaries. Since the approach includes a combination of direct measurement and modeling, we also describe circumstances under which the model can be shown to be inappropriate. Examples with several micro-benchmark applications (for which the true measurement is known) and an application that uses Monte Carlo techniques to solve Lap lace's equation are used for illustrative purposes.

Architecturally-diverse systems (containing co-processors such as reconfigurable logic and graphics engines) have received significant attention recently in the high performance computing community. They are new enough, however, that application development tools are quite limited. This paper describes our performance measurement system, Time Trial, that automates performance measurements of diverse, streaming data applications. Time Trial enables low-impact measurements by interpreting performance queries in the Time Trial language and by compiling these queries to highly-specific, optimized instrumentation that aggressively performs lossy compression on the performance meta-data. Currently, Time Trial supports multi-core processors and reconfigurable logic, with GPU support under development. We present the Time Trial language and its associated compiler, including its use in optimizing the performance of an example computational science problem.

Bloom filters are a probabilistic technique for large-scale set membership tests. They exhibit no false negative test results but are susceptible to false positive results. They are well-suited to both large sets and large numbers of membership tests. We implement the Bloom filters present in an accelerated version of BLAST, a genome biosequence alignment application, on NVIDIA GPUs and develop an analytic performance model that helps potential users of Bloom filters to quantify the inherent tradeoffs between throughput and false positive rates.

Magnetologic circuits are digital logic circuits constructed using magnetic tunnel junction (MTJ) devices. These devices are non-volatile, robust, and scale favorably with process dimensions. Several approaches exist for building magnetologic circuits. We are investigating current-mode magnetologic circuits as a viable option. Current-mode circuits avoid charging/ discharging load capacitances and can be used to program a downstream device. Noise in a current-mode read circuit can affect the ability to correctly distinguish logic states in an MTJ. In this paper, we present a noise analysis of a current-mode read circuit or current conveyor. We derive analytical noise equations and verify them via simulation.

Many compute-bound applications have seen order-of-magnitude speedups using special-purpose accelerators. FPGAs in particular are good at implementing recurrence equations realized as arrays. Existing high-level synthesis approaches for recurrence equations produce an array that is latency-space optimal. We target applications that operate on a large collection of small inputs, e.g. a database of biological sequences, where overall throughput is the most important measure of performance. In this work, we introduce a new design-space exploration procedure within the polyhedral framework to optimize throughput of a systolic array subject to area and bandwidth constraints of an FPGA device. Our approach is to exploit additional parallelism by pipelining multiple inputs on an array and multiple iteration vectors in a processing element. We prove that the throughput of an array is given by the inverse of the maximum number of iteration vectors executed by any processor in the array, which is determined solely by the array's projection vector. We have applied this observation to discover novel arrays for Nussinov RNA folding. Our throughput-optimized array is 2× faster than the standard latency-space optimal array, yet it uses 15% fewer LUT resources. We achieve a further 2× speedup by processor pipelining, with only a 37% increase in resources. Our tool suggests additional arrays that trade area for throughput and are 4-5× faster than the currently used latency-optimized array. These novel arrays are 70-172× faster than a software baseline.

Streaming is a highly effective paradigm for expressing parallelism in high-throughput applications. A streaming computation is a network of compute nodes connected by unidirectional FIFO channels. When these computations are mapped onto real parallel platforms, however, some computations, especially ones in which some nodes act as filters, can deadlock the system due to finite buffering on channels. In this paper, we focus on streaming computations which contain a commonly used structure called split-join. Based on our previous work, we propose two correct deadlock-avoidance algorithms, named the Propagating Algorithm and the Non-propagating Algorithm. Our evaluation of two representative applications, biological sequence alignment and random number generation, shows that the Non-propagating Algorithm has very small communication overhead. For systems with large buffers or a low filtering ratio, the communication overhead of the Non-propagating Algorithm is negligible.

RNA folding is a compute-intensive task that lies at the core of search applications in bioinformatics such as RNAfold and UNAFold. In this work, we analyze the Zuker RNA folding algorithm, which is challenging to accelerate because it is resource intensive and has a large number of variable-length dependencies. We use a technique of Lyngso to rewrite the recurrence in a form that makes polyhedral analysis more effective and use data pipelining and tiling to generate a hardware-friendly implementation. Compared to earlier work, processors in our array are more efficient and use fewer logic and memory resources. We implemented our array on a Xilinx Virtex 4 LX100-12 FPGA and experimentally verified a 103x speedup over a single core of a 3 GHz Intel Core 2 Duo CPU. The accelerator is also 17x faster than a recent Zuker implementation on a Virtex 4 LX200-11 FPGA and 12x and 6x faster respectively than an Nvidia Tesla C870 and GTX280 GPU. We conclude with a number of lessons in using FPGAs to implement arrays after polyhedral analysis. We advocate using polyhedral analysis to accelerate other dynamic programming recurrences in computational biology.

Many compute-bound software applications have seen order-of-magnitude speedups using application-specific accelerators built on specialized architectures such as field-programmable gate arrays. These architectures are particularly good at implementing systems of recurrence equations realized as systolic arrays. We pursue high-level synthesis tools for recurrence equations that can search the space of possible parallel array designs to optimize various design criteria. Most existing approaches produce an array that is latency-space optimal. We target applications that operate on a large collection of small inputs, e.g. a database of biological sequences. For these applications, overall throughput, rather than latency per input, is the most important measure of performance.

The paradigm of computation on streaming data has received considerable recent attention. Streaming computations can be efficiently parallelized using systems of computing nodes organized in dataflow-like architectures. However, when these nodes have the ability to filter, or discard, some of their inputs, a system with finite buffering is vulnerable to deadlock. In this paper, we formalize a model of streaming computation systems with filtering describe precisely the conditions under which such systems may deadlock, and propose provably correct mechanisms to avoid deadlock. Our approach relies on adding extra "dummy" tokens to the data streams and does not require global run-time coordination among nodes or dynamic resizing of buffers. This approach is particularly well-suited to preventing deadlock in distributed systems of diverse computing architectures, where global coordination or modification of buffer sizes may be difficult or impossible in practice.

Many computation kernels that analyze large data streams can be accelerated by converting their recurrences to parallel systolic arrays. Application domains such as bioinformatics seek to minimize the total time to analyze a large set of discrete small inputs. While traditional methods for array synthesis produce a single most efficient array design, modern computational platforms support fast runtime reconfiguration that can choose among a collection of arrays optimized for different input characteristics, such as input size. In this work, we give dynamic programming algorithms to efficiently select a few array implementations from a large set of candidates so as to minimize total execution time on a dataset with a known distribution of input sizes. We apply our methods to accelerate the Nussinov RNA folding algorithm on a Xilinx Virtex 4 FPGA. Using runtime reconfiguration among five array instantiations, we are able to process a database of 2.7 billion RNA bases in 72 seconds, which is 48% faster than using a single array and 252times faster than comparable software. We demonstrate substantial efficiency benefits even when the input length distribution is biased toward low-throughput arrays, when reconfiguration time is as large as half a second, and when only a small number of distinct arrays may be used.

RNA structure prediction, or folding, is a compute-intensive task that lies at the core of several search applications in bioinformatics. We begin to address the need for high-throughput RNA folding by accelerating the Nussinov folding algorithm using a 2D systolic array architecture. We adapt classic results on parallel string parenthesization to produce efficient systolic arrays for the Nussinov algorithm, elaborating these array designs to produce fully realized FPGA implementations. Our designs achieve estimated speedups up to 39times on a Xilinx Virtex-II 6000 FPGA over a modern x86 CPU.

Pipelined computing applications often have their performance modeled using queueing techniques. While networks with infinite capacity queues have well understood properties, networks with finite capacity queues and blocking between servers have resisted closed-form solutions and are typically analyzed with approximate solutions. It is this latter case that more closely represents the circumstances present for pipelined computation. In this paper, we extend an existing approximate solution technique and, more importantly, provide guidance as to when the approximate solutions work well and when they fail.

Significant performance gains have been reported by exploiting the specialized characteristics of hybrid computing architectures for a number of streaming applications. While it is straightforward to physically construct these hybrid systems, application development is often quite difficult. We have built an application development environment, Auto-Pipe, that targets streaming applications deployed on hybrid architectures. Here, we describe some of the current and future characteristics of the Auto-Pipe environment that facilitate an understanding of the performance of an application that is deployed on a hybrid system.

Large-scale protein sequence comparison is an important but compute-intensive task in molecular biology. BLASTP is the most popular tool for comparative analysis of protein sequences. In recent years, an exponential increase in the size of protein sequence databases has required either exponentially more running time or a cluster of machines to keep pace. To address this problem, we have designed and built a high-performance FPGA-accelerated version of BLASTP, Mercury BLASTP. In this paper, we describe the architecture of the portions of the application that are accelerated in the FPGA, and we also describe the integration of these FPGA-accelerated portions with the existing BLASTP software. We have implemented Mercury BLASTP on a commodity workstation with two Xilinx Virtex-II 6000 FPGAs. We show that the new design runs 11-15 times faster than software BLASTP on a modern CPU while delivering close to 99% identical results.

BLASTP is the most popular tool for comparative analysis of protein sequences. In recent years, an exponential increase in the size of protein sequence databases has required either exponentially more runtime or a cluster of machines to keep pace. To address this problem, we have designed and built a high-performance FPGA-accelerated version of BLASTP, Mercury BLASTP. In this paper, we focus on seed generation, the first stage of the BLASTP algorithm. Our seed generator is capable of processing database residues at up to 219 Mresidues/second for 2048- residue queries. The full Mercury BLASTP pipeline, including our seed generator, achieves a speedup of 37times over the popular NCBI BLASTP software on a 2.8 GHz Intel P4 CPU, with sensitivity more than 99% that of the software. Our architecture can be generalized to accelerate the seed generation stage in other important biocomputing applications.

Large-scale protein sequence comparison is an important but compute-intensive task in molecular biology. The popular BLASTP software for this task has become a bottleneck for proteomic database search. One third of this software's time is spent executing the Smith-Waterman dynamic programming algorithm. This work describes a novel FPGA design for banded Smith-Waterman, an algorithmic variant tuned to the needs of BLASTP. This design has been implemented in Mercury BLASTP, our FPGA-accelerated version of the BLASTP algorithm. We show that Mercury BLASTP runs 6-16 times faster than software BLASTP on a modern CPU while delivering 99% identical results.

Comparison between biosequences and probabilistic models is an increasingly important part of modern DNA and protein sequence analysis. The large and growing number of such models in today's databases demands computational approaches to searching these databases faster, while maintaining high sensitivity to biologically meaningful similarities. This work describes an FPGA-based accelerator for comparing proteins to hidden Markov models of the type used to represent protein motifs in the popular HM-MER motif finder. Our engine combines a systolic array design with enhancements to pipeline the complex Viterbi calculation that forms the core of the comparison, and to support coarse-grained parallelism and streaming of multiple sequences within one FPGA. Performance estimates based on a functioning VHDL realisation of our design show a 190 times speedup over the same computation in optimised software on a modern general-purpose CPU.

Hybrid systems consisting of a multitude of different computing device types are interesting targets for high-performance applications. Chip multiprocessors, FPGAs, DSPs, and GPUs can be readily put together into a hybrid system; however, it is not at all clear that one can effectively deploy applications on such a system. Coordinating multiple languages, especially very different languages like hardware and software languages, is awkward and error prone. Additionally, implementing communication mechanisms between different device types unnecessarily increases development time. This is compounded by the fact that the application developer, to be effective, needs performance data about the application early in the design cycle. We describe an application development environment specifically targeted at hybrid systems, supporting data-flow semantics between application kernels deployed on a variety of device types. A specific feature of the development environment is the availability of performance estimates (via simulation) prior to actual deployment on a physical system.

Currently available genome databases are growing exponentially in size, making it difficult for software analysis tools to keep up. A number of hardware accelerators utilizing special purpose VLSI (Blas, et al., 2005) or reconfigurable hardware (Hoang, 1993) have been proposed. However, they are inflexible; support for new applications usually requires a laborious redesign. None of these accelerators can be easily adapted to other applications that require differing hardware resources. The design philosophy of the softcore vector processor is based on two important goals: adaptability and performance. Instruction based execution allows programmable support for a large number of algorithms. The fact that different classes of applications require different subsets of hardware resources, argues for a customizable hardware design built from primitives. The second goal was to achieve programmability without sacrificing performance. The SVP was designed to perform competitively with full custom solutions available in the market

Profile Hidden Markov models (HMMs) are a powerful approach to describing biologically significant functional units, or motifs, in protein sequences. Entire databases of such models are regularly compared to large collections of proteins to recognize motifs in them. Exponentially increasing rates of genome sequencing have caused both protein and model databases to explode in size, placing an ever-increasing computational burden on users of these systems.Here, we describe an accelerated search system that exploits parallelism in a number of ways. First, the application is functionally decomposed into a pipeline, with distinct compute resources executing each pipeline stage. Second, the first pipeline stage is deployed on a systolic array, which yields significant fine-grained parallelism. Third, for some instantiations of the design, parallel copies of the first pipeline stage are used, further increasing the level of coarse-grained parallelism.A naïve parallelization of the first stage computation has serious repercussions for the sensitivity of the search. We present a pair of remedies to this dilemma and quantify the regions of interest within which each approach is most effective. Analytic performance models are used to assess the overall speedup that can be attained relative to a single-processor software solution. Performance improvements of 1 to 2 orders of magnitude are predicted.

In the liquid architecture project, we are exploring ways in which architectural flexibility can be exploited to improve the execution properties of individual applications. Here, we report on successes we have had to date in this area, and present our vision of where this research should proceed into the future.

Applications for constrained embedded systems are subject to strict time constraints and restrictive resource utilization. With soft core processors, application developers can customize the processor for their application, constrained by resources but aimed at high application performance. With such freedom in the design space of the processor, however, comes complexity. We present here an automatic optimization technique that helps the developers with the processor microarchitecture customization. A naive approach exploring all possible configurations is exponential with the number of parameters and hence is clearly infeasible, even with only tens of reconfigurable parameters. Instead, our approach runs in time that is linear with the number of parameter values, based on an assumption of parameter independence. This makes the approach feasible and scalable. For the dimensions that we customize, namely application runtime and hardware resources, we formulate their costs as a constrained binary integer nonlinear optimization program. Though the results are not guaranteed to be optimal, we find they are near-optimal in practice. Our technique itself is general and can be applied to other design-space exploration problems

A dedicated cluster is often not fully utilized even when all of its processors are allocated to jobs. This occurs any time that a running job does not use 100% of each of the processors allocated to it. We increase the throughput and efficiency of the cluster by scheduling background jobs to run concurrently with the "primary" jobs originally scheduled on the cluster. We do this while maintaining the quality of service provided to the primary jobs. Our results come from empirical measurements using production applications.

Methods for estimating the clutter scattering function and detecting ground moving targets, using pulse-Doppler surveillance radar data, are described. The imaging problem is cast as one of structured covariance estimation with time-varying measurement models and illumination patterns. An expectation-maximization (EM) algorithm is derived and the computational issues arising from its use are discussed. The detection algorithm uses the estimated clutter statistics and a time-varying target model in a standard generalized likelihood ratio test (GLRT).

This paper presents a general system architecture tailored to perform searching, filtering, compression, encryption, and other operations on unstructured data streaming from a disk system. The system achieves high performance on such applications by providing for parallelism, hardware-application specialization and reconfiguration, and hardware placement near the disk systems. A limited prototype of a single compute node has been implemented and is described. The prototype is tailored to applications involving complex searching and its performance is compared to a pure software implementation having the same search capabilities. Performance is considered in terms of data set size, query string hit rate and query complexity. Performance results as a function of these parameters are presented and the results indicate that, for data set sizes above 1.4 MB, the prototype compute node is between one and two orders of magnitude faster than a pure software implementation. At high data set sizes, on an individual node, speedups of about 200 and a sustained throughput of 300 MB/sec have been achieved.

Summary form only given. Data mining is an application that is commonly executed on massively parallel systems, often using clusters with hundreds of processors. With a disk-based data store, however, the data must first be delivered to the processors before effective mining can take place. Here, we describe the prototype of an experimental system that moves processing closer to where the data resides, on the disk, and exploits massive parallelism via reconfigurable hardware to perform the computation. The performance of the prototype is also reported.

This paper considers a class of embedded signal processing applications. To achieve real-time performance these applications must be executed on a parallel processor. The paper focuses on the multiring optical interconnection network used in the system and specifically on the performance gains associated with utilizing the bandwidth reconfiguration capabilities associated with the network. The network is capable of being reconfigured to provide designated bandwidths to different source-destination connections both across rings and within a ring. The applications each consist of a sequence of alternating communication and computation phases. The sequence continues until execution of the application is complete. The effect of reconfiguration on application performance is explored using simulation techniques. The results indicate that substantial performance gains (speedups of 2 or more) can be achieved for this application class.

The implementation of computational systems to perform challenging operations often involves balancing the performance specification, system throughput, and available system resources. For problems of automatic target recognition (ATR), these three quantities of interest are the probability of classification error, the rate at which regions of interest are processed, and the capabilities of the underlying hardware (which is a function of the available computational resources and available power). An understanding of the inter-relationships between these factors can be an aid in making informed choices while exploring competing design possibilities. Combining characterizations of ATR performance, which yield probability of classification error as a function of target model complexity, with analytical models of computational performance, which yield throughput as a function of target model complexity and available resources, we can form a set of parametric curves which relate the quality of the results to the resources consumed.

The Gemini interconnect is a dual technology (optical and electrical) interconnection network designed for use in tightly-coupled multicomputer systems. It consists of a circuit-switched optical data path in parallel with a packet-switched electrical control/data path. The optical path is used for transmission of long data messages and the electrical path is used for switch control and transmission of short data messages. The paper describes the architecture of the interconnection network and related communications protocols. Fairness issues associated with network operation are addressed and a discrete-event simulation model of the entire system is described. Network performance characteristics derived from the simulation model are presented. The results show significant performance benefits when using virtual output queuing and quantify the tradeoffs between throughput and fairness in the system.

Existing fair scheduling schemes have focused primarily on scheduling multiple flows to a single output. The limited work that has focused on scheduling multiple flows to multiple outputs has assumed a non-blocking, slotted-time, cell-based network with a centralized controller. This paper presents a fair scheduler suitable for use in bufferless circuit-switched blocking networks operating with distributed, asynchronous controllers and variable length messages. We begin by describing the potential for starvation in the Gemini interconnect network, an optical, circuit-switched network. A proposed distributed fair scheduler is presented and shown to solve this problem. The tradeoffs and limitations of performing many-to-many fair scheduling in general, and that of our fair scheduler in particular, are discussed.

Abstract – Design verification via simulation is an im-portant component in the development of digital systems. However, with continuing increases in the capabilities of VLSI systems, the simulation task has become a significant bottleneck in the design process. As a result, researchers are attempting to exploit parallel processing techniques to improve the performance of VLSI logic simulation. This tutorial describes the current state-of-the-art in parallel logic simulation, including parallel simulation techniques, factors that impact simulation performance, performance results to date, and the directions currently being pursued by the research community. I.

A performance model for a globally-clocked, discrete-event queueing network simulator is developed and validated against measured results. The use of architectural enhancements for improving the performance of the algorithm is investigated. Both scaled and fixed problem sizes are investigated, with a maximum measured scaled speedup of 47 and 64 processors. The model is very accurate, predicting runtime within 5% of measured results.

A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log/sub 2/P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic.>

Simulated annealing for obtaining approximate solutions to combinatorial optimization problems is addressed. The serial algorithm, however, can require extensive computation time. Most parallel algorithms for simulated annealing are problem-specific and/or violate the serial decision sequence, thereby allowing errors not present in the serial algorithm. Maintaining the serial sequence is necessary to prove that the algorithm converges to a global optimum solution when allowed to reach equilibrium at each temperature. A parallel algorithm which is both problem-independent and maintains the serial decision sequence is presented. The parallel algorithm uses the concurrency techniques of speculative computation to achieve speedup which can exceed log/sub 2/P, on P processors. For three problems investigated, the average speedup on eight processors was 2.6.>

A performance model for a hierarchical discrete-event-simulation algorithm running on a hypercube architecture is presented. A static allocation of system components to hypercube processors and a global clock algorithm with an event-based time increment are assumed. The model is applied to a digital systems simulation. The effects of different architectures, algorithm parameter values, and partitioning strategies on speedup are evaluated.>

The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log/sub 2/N and (N+log/sub 2/N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.>

The high costs associated with logic simulation of large VLSI based systems have led to the need for new computer architectures tailored to the simulation task. Such architecture have the potential for significant speedups over standard software based logic simulators. Several commercial simulation engines have been produced to satisfy need in this area. To properly explore the space of alternative simulation architectures, data is required on the simulation process itself. This paper presents a framework for such data gathering activity by first examining possible sources of speedup in the logic simulation task, examining the sort of data needed in the design of simulation engines, and then presenting such data. The data contained in the paper includes information on the subtask times found in standard discrete event simulation algorithms, event intensities, queue length distributions and simultaneous event distributions.

Design of high-performance hardware and software-based gate-switch-level logic simulators requires knowledge about the logic simulation process itself. Unfortunately, little data is publicly available concerning key aspects of this process. An example of this is the lack of published empirical measurements relating to the time distribution of events generated by such simulators. This paper presents a gate-switch-level logic simulator lsim which is oriented towards the collection of data about the simulation process. The basic components of lsim are reviewed, and its relevant data gathering facilities are discussed. An example is presented which illustrates the use of lsim in gathering data on event distributions and on communications requirements under alternative logic circuit partitionings.