Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Distributed Embedded Systems (2)
- Logic simulation (2)
- Real-Time Middleware (2)
- AHE (1)
- Adaptive and reflective middleware (1)
-
- Adaptive real-time image transmission. (1)
- Algorithms (1)
- Anytime algorithms (1)
- Beat Analysis (1)
- Branch-and-bound (1)
- Branch-and-cut (1)
- Circuit simulation (1)
- Composite structures (1)
- Contrast-enhancement (1)
- Data collection to cloud (1)
- Denial of Service (1)
- Design (1)
- Discrete event simulation (1)
- Distributed real-time and embedded middleware (1)
- Distributed systems (1)
- Event list algorithms (1)
- Event lists (1)
- Execution Security (1)
- Experimentation (1)
- First order logic. (1)
- Generative programming (1)
- Group Scheduling (1)
- Linear programming (1)
- Logic simulation machines (1)
- Logic simulators (1)
- Publication Year
Articles 91 - 120 of 683
Full-Text Articles in Computer Engineering
Performance Tuning Of Streaming Applications Via Search-Space Decomposition, Shobana Padmanabhan, Roger D. Chamberlain, Yixin Chen
Performance Tuning Of Streaming Applications Via Search-Space Decomposition, Shobana Padmanabhan, Roger D. Chamberlain, Yixin Chen
All Computer Science and Engineering Research
High-performance streaming applications are typically pipelined and deployed on architecturally diverse (hybrid)systems. Developers of such applications are interested in customizing components used, so as to benefit application performance. We present an efficient and automatic technique for design-space exploration of applications in this problem domain. We solve performance tuning as an optimization problem by formulating cost functions using results from queueing theory. This results in a mixed-integer nonlinear optimization problem which is NP-hard. We reduce the search complexity by decomposing the search space. We have developed a domain-specific decomposition technique using topological information of the application embodied in the queueing network …
Global Constructive Optimization Of Vascular Systems, Manfred Georg, Tobias Preusser, Horst K. Hahn
Global Constructive Optimization Of Vascular Systems, Manfred Georg, Tobias Preusser, Horst K. Hahn
All Computer Science and Engineering Research
We present a framework for the construction of vascular systems based on optimality principles of theoretical physiology. Given the position and flow distribution of end points of a vascular system, we construct the topology and positions of internal nodes to complete the vascular system in a realistic manner. Optimization is driven by intravascular volume minimization with constraints derived from physiological principles. Direct optimization of a vascular system, including topological changes, is used instead of simulating vessel growth. A good initial topology is found by extracting key information from a previously optimized model with less detail. This technique is used iteratively …
Sorting As A Streaming Application Executing On Chip Multiprocessors, Roger D. Chamberlain, Greg A. Galloway, Mark A. Franklin
Sorting As A Streaming Application Executing On Chip Multiprocessors, Roger D. Chamberlain, Greg A. Galloway, Mark A. Franklin
All Computer Science and Engineering Research
Expressing concurrency in applications has always been a difficult and error-prone endeavor, yet effective utilization of multi-core processors requires that the concurrency in applications be understood. One approach to the expression of concurrency is streaming, which has shown real promise as a safe and effective method for many application classes. Here, we express a classic problem, sorting, in the streaming paradigm and explore the implications of various algorithm and architectural design parameters on the performance of the application.
Priority Assignment For Real-Time Flows In Wirelesshart Sensor-Actuator Networks, Abusayeed Saifullah, You Chenyang, Yixin Chen
Priority Assignment For Real-Time Flows In Wirelesshart Sensor-Actuator Networks, Abusayeed Saifullah, You Chenyang, Yixin Chen
All Computer Science and Engineering Research
Recent years have witnessed the adoption of wireless sensor-actuator networks as a communication infrastructure for process control applications. An important enabling technology for industrial process control is WirelessHART, an open wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced byWirelessHART networks is to meet the stringent real-time communication requirements imposed by feedback control systems in process industries. Fixed priority scheduling, a popular scheduling policy in real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a major impact on the schedulability of real-time flows in these …
End-To-End Delay Analysis For Fixed Priority Scheduling In Wirelesshart Networks, Abusayeed Saifullah, You Xu, Chenyang Lu, Yixin Chen
End-To-End Delay Analysis For Fixed Priority Scheduling In Wirelesshart Networks, Abusayeed Saifullah, You Xu, Chenyang Lu, Yixin Chen
All Computer Science and Engineering Research
The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis of the real-time flows that are scheduled using a fixed …
Split And Merge Functions For Supporting Multiple Processing Pipelines In Mercury Blastn, Jwalant Ahir, Jeremy Buhler, Roger D. Chamberlain
Split And Merge Functions For Supporting Multiple Processing Pipelines In Mercury Blastn, Jwalant Ahir, Jeremy Buhler, Roger D. Chamberlain
All Computer Science and Engineering Research
Biosequence similarity search is an important application in computational biology. Mercury BLASTN, an FPGA-based implementation of BLAST for DNA, is one of the alternatives for fast DNA sequence comparison. The re-design of BLAST into a streaming application combined with a high-throughput hardware pipeline have enabled Mercury BLAST to emerge as one of the fastest implementations of bio-sequence similarity search. This performance can be further enhanced by exploiting the data-level parallelism present within the application. Here we present a multiple FPGA-based Mercury BLASTN design in order to double the speed and throughput of DNA sequence computation. This paper describes a dual …
Toward A Two-Tier Clinical Warning System For Hospitalized Patients, Gregory Hackmann, Minmin Chen, Octav Chipara, Chenyang Lu, Yixin Chen, Marin Kollef, Thomas C. Bailey
Toward A Two-Tier Clinical Warning System For Hospitalized Patients, Gregory Hackmann, Minmin Chen, Octav Chipara, Chenyang Lu, Yixin Chen, Marin Kollef, Thomas C. Bailey
All Computer Science and Engineering Research
Clinical study has found early detection and intervention to be essential for preventing clinical deterioration in patients at general hospital units. In this paper, we envision a two-tiered early warning system designed to identify the signs of clinical deterioration and provide early warning of serious clinical events. The first tier of the system automatically identifies patients at risk of clinical deterioration from existing electronic medical record databases. The second tier performs real-time clinical event detection based on real-time vital sign data collected from on-body wireless sensors attached to those high-risk patients. We employ machine-learning techniques to analyze data from both …
Optimal Design-Space Exploration Of Streaming Applications, Shobana Padmanabhan, Yixin Chen, Roger D. Chamberlain
Optimal Design-Space Exploration Of Streaming Applications, Shobana Padmanabhan, Yixin Chen, Roger D. Chamberlain
All Computer Science and Engineering Research
Many embedded and scientific applications are frequently pipelined asynchronously and deployed on architecturally diverse systems to meet performance requirements and resource constraints. We call such pipelined applications streaming applications. Typically, there are several design parameters in the algorithms and architectures used that, when customized, impact the tradeoff between different metrics of application performance as well as resource utilization. Automatic 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. We present a global optimization framework comprising a novel domain-specific variation of branch-and-bound that …
An Inexpensive Robot Platform For Teleoperation And Experimentation, Daniel A. Lazewatsky, William D. Smart
An Inexpensive Robot Platform For Teleoperation And Experimentation, Daniel A. Lazewatsky, William D. Smart
All Computer Science and Engineering Research
Most commercially-available robots are either aimed at the research community, or are designed with a single purpose in mind. The extensive hobbyist community has tended to focus on the hardware and the low-level software aspects. We claim that there is a need for a low-cost, general-purpose robot, accessible to the hobbyist community, with sufficient computation and sensing to run ``research-grade'' software. In this paper, we describe the design and implementation of such a robot. We explicitly outline our design goals, and show how a capable robot can be assembled from off-the-shelf parts, for a modest cost, by a single person …
Against All Probabilities: A Modeling Paradigm For Streaming Applications That Goes Against Common Notions, Rahav Dor
All Computer Science and Engineering Research
Hardware and software design requires the right portion of skills and mental faculties. The design of a good system is an exercise in rational thinking, engineering, and art. The design process is further complicated when we aspire to build systems that exploit parallelism or are targeted to be deployed on architecturally diverse computing devices, FPGAs or GPUs to name just a few. The need to develop systems that can take advantage of computing devices beyond general purpose CPUs is real. There are several application domains and research efforts that will simply not be able to adequately perform or yield answers …
Arch: Practical Channel Hopping For Reliable Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu
Arch: Practical Channel Hopping For Reliable Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu
All Computer Science and Engineering Research
Home area networks (HANs) promise to enable sophisticated home automation applications such as smart energy usage and assisted living. However, recent empirical study of HAN reliability in real-world residential environments revealed significant challenges to achieving reliable performance in the face of significant and variable interference from a multitude of coexisting wireless devices. We propose the Adaptive and Robust Channel Hopping (ARCH) protocol: a lightweight receiveroriented protocol which handles the dynamics of residential environments by reactively channel hopping when channel conditions have degraded. ARCH has several key features. First, ARCH is an adaptive protocol that channel-hops based on changes in channel …
Multi-Channel Reliability And Spectrum Usage In Real Homes: Empirical Studies For Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu
Multi-Channel Reliability And Spectrum Usage In Real Homes: Empirical Studies For Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu
All Computer Science and Engineering Research
Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced by HANs is maintaining reliable operation in real-world residential environments. This paper presents two in-depth empirical studies on the wireless channels in real homes. The spectrum study analyzes the spectrum usage in the 2.4 GHz band where wireless sensor networks based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through passive spectrum analysis across the entire 2.4 GHz band over …
The Design And Implementation Of Mcflow: A Real-Time Multi-Core Aware Middleware For Dependent Task Graphs, Huang-Ming Huang, Christopher Gill, Chenyang Lu
The Design And Implementation Of Mcflow: A Real-Time Multi-Core Aware Middleware For Dependent Task Graphs, Huang-Ming Huang, Christopher Gill, Chenyang Lu
All Computer Science and Engineering Research
Modern computer architectures have evolved from uni-processor platforms to multi-processor and multi-core plat- forms, but traditional real-time distributed middleware such as RT-CORBA has not kept pace with that evolution. To address those issues, this paper describes the design and implementation of MCFlow, a new real-time distributed middleware for dependent task graphs running on multi-core platforms. MCFlow provides the following contributions to the state of the art in real-time middleware: (1) it provides an efficient C++ based component model through which computations can be configured flexibly for execution within a single core, across cores of a common host, or spanning multiple …
What Do Collaborations With The Arts Have To Say About Human-Robot Interaction?, William D. Smart, Annamaria Pileggi, Leila Takayama
What Do Collaborations With The Arts Have To Say About Human-Robot Interaction?, William D. Smart, Annamaria Pileggi, Leila Takayama
All Computer Science and Engineering Research
This is a collection of papers presented at the workshop "What Do Collaborations with the Arts Have to Say About HRI", held at the 2010 Human-Robot Interaction Conference, in Osaka, Japan.
Multi-Tier Diversified Service Architecture For Internet 3.0: The Next Generation Internet, Subharthi Paul, Raj Jain, Jianli Pan, Chakchai So-In
Multi-Tier Diversified Service Architecture For Internet 3.0: The Next Generation Internet, Subharthi Paul, Raj Jain, Jianli Pan, Chakchai So-In
All Computer Science and Engineering Research
The next generation Internet needs to support multiple diverse application contexts. In this paper, we present Internet 3.0, a diversified, multi-tier architecture for the next generation Internet. Unlike the current Internet, Internet 3.0 defines a new set of primitives that allows diverse applications to compose and optimize their specific contexts over resources belonging to multiple ownerships. The key design philosophy is to enable diversity through explicit representation, negotiation and enforcement of policies at the granularity of network infrastructure, compute resources, data and users. The basis of the Internet 3.0 architecture is a generalized three-tier object model. The bottom tier consists …
Cloud Computing For Scalable Planning By Stochastic Search, Qiang Lu, You Xu, Ruoyun Huang, Yixin Chen
Cloud Computing For Scalable Planning By Stochastic Search, Qiang Lu, You Xu, Ruoyun Huang, Yixin Chen
All Computer Science and Engineering Research
Graph search has been employed by many AI techniques and applications. A natural way to improve the efficiency of search is to utilize ad- vanced, more powerful computing platforms. However, expensive computing infrastructures, such as supercomputers and large-scale clusters, are traditionally available to only a limited number of projects and researchers. As a results, most AI applications, with access to only commodity com- puters and clusters, cannot benefit from the efficiency improvements of high-performance parallel search algorithms. Cloud computing provides an attractive, highly accessible alternative to other traditional high- performance computing platforms. In this paper, we first show that the …
Optimal Time Utility Based Scheduling Policy Design For Cyber-Physical Systems , Terry Tidwell, Robert Glaubius, Christopher D. Gill, William D. Smart
Optimal Time Utility Based Scheduling Policy Design For Cyber-Physical Systems , Terry Tidwell, Robert Glaubius, Christopher D. Gill, William D. Smart
All Computer Science and Engineering Research
Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, optimal utility accrual scheduling design is needed for real-time cyber-physical domains. In this paper we design optimal utility accrual scheduling policies for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process formulation of the scheduling problem. We use this formulation to …
A Scalable Method For Solving High-Dimensional Continuous Pomdps Using Local Approximation, Tom Erez, William D. Smart
A Scalable Method For Solving High-Dimensional Continuous Pomdps Using Local Approximation, Tom Erez, William D. Smart
All Computer Science and Engineering Research
Partially-Observable Markov Decision Processes (POMDPs) are typically solved by finding an approximate global solution to a corresponding belief-MDP. In this paper, we offer a new planning algorithm for POMDPs with continuous state, action and observation spaces. Since such domains have an inherent notion of locality, we can find an approximate solution using local optimization methods. We parameterize the belief distribution as a Gaussian mixture, and use the Extended Kalman Filter (EKF) to approximate the belief update. Since the EKF is a first-order filter, we can marginalize over the observations analytically. By using feedback control and state estimation during policy execution, …
Augmented Lagrangian Algorithms Under Constraint Partitioning, You Xu, Yixin Chen
Augmented Lagrangian Algorithms Under Constraint Partitioning, You Xu, Yixin Chen
All Computer Science and Engineering Research
We present a novel constraint-partitioning approach for solving continuous nonlinear optimization based on augmented Lagrange method. In contrast to previous work, our approach is based on a new constraint partitioning theory and can handle global constraints. We employ a hyper-graph partitioning method to recognize the problem structure. We prove global convergence under assumptions that are much more relaxed than previous work and solve problems as large as 40,000 variables that other solvers such as IPOPT [11] cannot solve.
Geodesic Grassfire For Computing Mixed-Dimensional Skeletons, Lu Liu, Tao Ju
Geodesic Grassfire For Computing Mixed-Dimensional Skeletons, Lu Liu, Tao Ju
All Computer Science and Engineering Research
Skeleton descriptors are commonly used to represent, understand and process shapes. While existing methods produce skeletons at a fixed dimension, such as surface or curve skeletons for a 3D object, often times objects are better described using skeleton geometry at a mixture of dimensions. In this paper we present a novel algorithm for computing mixed-dimensional skeletons. Our method is guided by a continuous analogue that extends the classical grassfire erosion. This analogue allows us to identify medial geometry at multiple dimensions, and to formulate a measure that captures how well an object part is described by medial geometry at a …
The Virtual Network Scheduling Problem For Heterogeneous Network Emulation Testbeds, Charlie Wisemen, Jonathan Turner
The Virtual Network Scheduling Problem For Heterogeneous Network Emulation Testbeds, Charlie Wisemen, Jonathan Turner
All Computer Science and Engineering Research
Network testbeds such as Emulab and the Open Network Laboratory use virtualization to enable users to define end user virtual networks within a shared substrate. This involves mapping users' virtual network nodes onto distinct substrate components and mapping virtual network links onto substrate paths. The mappings guarantee that different users' activities can not interfere with one another. The problem of mapping virtual networks onto a shared substrate is a variant of the general graph embedding problem, long known to be NP-hard. In this paper, we focus on a more general version of the problem that supports advance scheduling of virtual …
Online Bayesian Analysis, Ruibin Xi, Yongjin Kim, Nan Lin, Yixin Chen, Gruia-Catalin Roman
Online Bayesian Analysis, Ruibin Xi, Yongjin Kim, Nan Lin, Yixin Chen, Gruia-Catalin Roman
All Computer Science and Engineering Research
In the last few years, there has been active research on aggregating advanced statistical measures in multidimensional data cubes from partitioned subsets of data. In this paper, we propose an online compression and aggregation scheme to support Bayesian estimations in data cubes based on the asymptotic properties of Bayesian statistics. In the proposed approach, we compress each data segment by retaining only the model parameters and a small amount of auxiliary measures. We then develop an aggregation formula that allows us to reconstruct the Bayesian estimation from partitioned segments with a small approximation error. We show that the Bayesian estimates …
Efficient Tracking Of Many Objects In Structured Environments, Nathan Jacobs, Michael Dixon, Scott Satkin, Robert Pless
Efficient Tracking Of Many Objects In Structured Environments, Nathan Jacobs, Michael Dixon, Scott Satkin, Robert Pless
All Computer Science and Engineering Research
We consider the special case of tracking objects in highly structured scenes. In the context of vehicle tracking in urban environments, we offer a fully automatic, end-to-end system that discovers and parametrizes the lanes along which vehicles drive, then uses just these pixels to simultaneously track dozens of objects. This system includes a novel active contour energy function used to parametrize the lanes of travel based only on the accumulation of spatio-temporal image derivatives, and a tracking algorithm that exploits longer temporal constraints made possible by our compact data representation; we believe both of these may be of independent interest. …
Throughput-Optimal Systolic Arrays From Recurrence Equations, Arpith C. Jacob, Jeremy D. Buhler, Roger D. Chamberlain
Throughput-Optimal Systolic Arrays From Recurrence Equations, Arpith C. Jacob, Jeremy D. Buhler, Roger D. Chamberlain
All Computer Science and Engineering Research
Many compute-bound software kernels have seen order-of-magnitude speedups on special-purpose accelerators built on specialized architectures such as field-programmable gate arrays (FPGAs). These architectures are particularly good at implementing dynamic programming algorithms that can be expressed as systems of recurrence equations, which in turn can be realized as systolic array designs. To efficiently find good realizations of an algorithm for a given hardware platform, we pursue software tools that can search the space of possible parallel array designs to optimize various design criteria. Most existing design tools in this area produce a design that is latency-space optimal. However, we instead wish …
Supercharged Planetlab Platform Architecture, Jonathan Turner, Patrick Crowley, John Dehart, Mart Haitjema, Fred Kuhns Kuhns, Ritun Patney, Michael Wilson, Charlie Wiseman, David Zar
Supercharged Planetlab Platform Architecture, Jonathan Turner, Patrick Crowley, John Dehart, Mart Haitjema, Fred Kuhns Kuhns, Ritun Patney, Michael Wilson, Charlie Wiseman, David Zar
All Computer Science and Engineering Research
This report describes the Supercharged Planetlab Platform (SPP), a system designed as a prototype of an internet-scale overlay hosting platform. Overlay networks have become an important vehicle for delivering Internet applications. Overlay network nodes are typically implemented using general purpose servers or clusters. The SPP offers a more integrated architecture, combining general-purpose servers with high performance Network Processor (NP) subsystems. SPP nodes have recently been deployed as part of the Global Environment for Network Innovation (GENI) and are available for use by research users.
Submodular Utility Optimization In Sensor Networks For Capacity Constraints, You Xu, Yixin Chen, Chenyang Lu, Sangeeta Bhattacharya, Abu Saifullah
Submodular Utility Optimization In Sensor Networks For Capacity Constraints, You Xu, Yixin Chen, Chenyang Lu, Sangeeta Bhattacharya, Abu Saifullah
All Computer Science and Engineering Research
With the fast development of wireless sensor network (WSN) technologies, WSNs have widely shifted from a specialized platform for a single application to an integrated infrastructure supporting multiple applications. It is hence a critical problem to allocate multiple applications to multiple sensors in order to maximize user utility subject to various resource constraints. The resulting constrained optimization problem is difficult since it is discrete, nonlinear, and not in closed-form. In this report, we develop an efficient optimization algorithm with rigorous approximation bounds for submodular monotonic optimization with multiple knapsack constraints. Based on a variance reduction formulation, we prove several important …
Feedback Thermal Control For Real-Time Systems, Yong Fu, Nicholas Kottenstette, Yingming Chen, Chenyang Lu, Xenofon D. Koutsoukos, Hongan Wang
Feedback Thermal Control For Real-Time Systems, Yong Fu, Nicholas Kottenstette, Yingming Chen, Chenyang Lu, Xenofon D. Koutsoukos, Hongan Wang
All Computer Science and Engineering Research
Thermal control is crucial to real-time systems as excessive processor temperature can cause system failure or unacceptable performance degradation due to hardware throttling. Real-time systems face significant challenges in thermal management as they must avoid processor overheating while still delivering desired real-time performance. Furthermore, many real-time systems must handle a broad range of uncertainties in system and environmental conditions. To address these challenges, this paper presents Thermal Control under Utilization Bound (TCUB), a novel thermal control algorithm specifically designed for real-time systems. TCUB employs a feedback control loop that dynamically controls both processor temperature and CPU utilization through task rate …
The Design And Performance Of Cyber-Physical Middleware For Real-Time Hybrid Structural Testing, Huang-Ming Huang, Xiuyu Gao, Terry Tidewell, Christopher Gill
The Design And Performance Of Cyber-Physical Middleware For Real-Time Hybrid Structural Testing, Huang-Ming Huang, Xiuyu Gao, Terry Tidewell, Christopher Gill
All Computer Science and Engineering Research
Real-time hybrid testing of civil structures, in which computational models and physical components must be integrated with high fidelity at run-time represents a grand challenge in the emerging area of cyber-physical systems. Actuator dynamics, complex interactions among computers and physical components, and computation and communication delays all must be managed carefully to achieve accurate tests. To address these challenges, we have developed a novel middleware for integrating cyber and physical components flexibly and with suitable timing behavior within a Cyber-physical Instrument for Real-time hybrid Structural Testing (CIRST). This paper makes three main contributions to the state of the art in …
Achieving Coordination Through Dynamic Construction Of Open Workflows ** Please See Wucse-2009-14 **, Louis Thomas, Justin Luner, Grui-Catalin Roman, Christopher Gill
Achieving Coordination Through Dynamic Construction Of Open Workflows ** Please See Wucse-2009-14 **, Louis Thomas, Justin Luner, Grui-Catalin Roman, Christopher Gill
All Computer Science and Engineering Research
Workflows, widely used on the Internet today, typically consist of a graph-like structure that defines the orchestration rules for executing a set of tasks, each of which is matched at run-rime to a corresponding service. The graph is static, specialized directories enable the discovery of services, and the wired infrastructure supports routing of results among tasks. In this paper we introduce a radically new paradigm for workflow construction and execution called open workflow. It is motivated by the growing reliance on wireless ad hoc networks in settings such as emergency response, field hospitals, and military operations. Open workflows facilitate goal-directed …
Design And Evaluation Of A Practical, High Performance Crossbar Scheduler, Jonathan Turner
Design And Evaluation Of A Practical, High Performance Crossbar Scheduler, Jonathan Turner
All Computer Science and Engineering Research
The Least Occupied Output First (LOOFA) scheduler is one of several unbuffered crossbar schedulers that provides strong performance guarantees when operated with a speedup of 2 or more. Because LOOFA requires the computation of a maximal matching, it has been considered too slow for use in systems with link rates of 10 Gb/s or more. This paper studies an approximate variant of LOOFA described briefly in [16]. We introduce a general family of schedulers that allows for partial sorting and that includes the LOOFA scheduler as a special case. We show that all schedulers in this class are work-conserving and …