The scalable coherent interface (SCI) is a newly established IEEE standard that provides bus-like services to a network of nodes without actually using a physical bus. Rather, it utilizes very fast, unidirectional links that can be arranged into a variety of topologies. SCI provides a novel fairness protocol that equally allocates bandwidth to all nodes on the network. When global fairness is not required, it is often desirable to relax its enforcement, in exchange for increased network utilization and better load balancing. This paper presents an extension to the SCI flow control protocol that increases network utilization and, hence, attainable system throughput by enforcing fairness only among nodes whose transmissions interfere with one another. The enhanced protocol grants a node as much bandwidth as it requires, as long as its transmissions do not inhibit those of other nodes. Although this is commonly known as max-min fairness, we more descriptively refer to it as relaxed fairness. We present extensive simulation results and compare them to the standard SCI protocol and to our desired performance, which has been preciously derived in the literature. The comparisons show that, on average, this enhancement can provide a substantial increase in performance over the original protocol.

This paper provides a methodology to decompose a complex network, containing primarily deterministic traffic, into isolated /spl Sigma/D/sub i//D/1 queuing models. We then present a new technique, Successive Superposition, to analyze the resulting models. In a /spl Sigma/D/sub i//D/1 queuing system, multiple streams of different bit rate, but constant length packets, arrive at a single high-speed multiplexer. Because of its application to Asynchronous Transfer Mode (ATM) switching nodes, previous /spl Sigma/D/sub i//D/1 analyses have assumed that stream arrivals are randomly staggered, and packets are served on a first-come-first-served basis. This work was, however, inspired primarily by the need for the accurate assessment of interprocessor communication costs in compile-time multiprocessor scheduling applications. For these applications, streams typically have known arrival times and must often be prioritized. This paper applies primarily to the class of digital signal processing and other application which can be represented by directed, acyclic precedence graphs. The analysis presented in this paper provides an exact characterization of the traffic, including service start times, queue sizes, and system departure times. We confirm the validity of our approach against simulation results. Finally, we demonstrate the utility of this work in a compile-time multiprocessor scheduling application.

The paper shows how to make efficient use of priority queues within a real-time multiprocessor system. Simulations show the effect of using priority queues at the entrance to the interprocessor communications network and in the packet switches within this network. Results demonstrate performance improvement when priority queues buffer data at the network entrances. However, results also show that the use of priority queues within the network may degrade performance.

Three modifications to the Boxes-ASE/ACE reinforcement learning improves implementation efficiency and performance. A state history queue (SHQ) eliminates computations for temporally insignificant states. A dynamic link table only allocates control memory to states the system traverses. CMAC state association uses previous learning to decrease training time. Simulations show a 4-fold improvement in learning. The SHQ in a hardware implementation of the pole-cart balancer reduces computation time 11-fold.>

Reliable priority-based flow-control is essential for real-time applications involving hard-deadlines. However, the use of first-in-first-out (FIFO) queues in such systems introduces priority inversion resulting in unbounded transmission delays. For this reason, a priority transmission queue is critical for multimedia and mission-critical systems. Yet very few priority queue implementations exist. This paper presents the design of a novel VLSI priority packet queue (PPQ), implemented in 1.2 /spl mu/m CMOS technology. It achieves fast operation by manipulating its contents in terms of packet segments, rather than individual words. Similar to paged memory, this new segmented architecture greatly reduces implementation cost by reusing segments and avoiding storage area fragmentation. By distributing the computationally intensive priority comparison operation over the access time for an entire segment, the PPQ achieves 96% of the speed of a high-speed packet FIFO. The PPQ can either perform priority inheritance or overwrite lower priority packets to minimize the impact of queue overflow. In addition, it is suitable as a general computer network interface buffer, since it robustly handles asynchronous read and write clocks of greatly disparate frequencies. Our initial implementation achieves well over twice the speed of a nonpipelined approach with minimal additional overhead. Furthermore, scaling this design to larger capacities and more priority levels results in an even greater improvement in speed over conventional approaches.>

Priority-based flow-control is essential for dead-line based real-time applications. First-in-first-out queues introduce priority inversion, which can cause unbounded delays. Yet very few priority queue implementations exist. This paper presents a novel 1.2 /spl mu/m CMOS priority packet queue that manipulates its contents in terms of packet segments, rather than individual words. Similar to paged memory, this architecture stores variable-sized packets, while avoiding storage area fragmentation. It significantly increases throughput by distributing the computationally intensive priority comparison operation over the access time for an entire segment. When full, the queue can either perform priority inheritance or overwrite lower priority packets. Its robust handling of a synchronous and disparate read and write clocks makes it suitable for use as a general network interface buffer. Our prototype achieves double the throughput of a conventional design, and larger capacity implementations promise even greater improvements.>

Real-time multiprocessor applications are typically characterized by hard deadlines which severely constrain interprocessor communications. Contention for communication resources and the use of first-in-first-out (FIFO) buffering can introduce priority inversion, resulting in missed deadlines. This paper investigates the scaling and performance of a novel 1.2 /spl mu/m CMOS Priority Packet Queue (PPQ) design. Its unique segmented architecture effectively exploits the packetized nature of traffic within most real-time networks and achieves 96% the speed of a high-speed packet FIFO. The PPQ can either perform priority inheritance or overwrite lower priority packets during queue overflow, and robustly handles asynchronous read and write clocks of widely disparate frequencies. Comparison results show that the PPQ offers over twice the speed of the conventional design, and promises even greater relative speed improvement for larger designs.>

The scalable coherent interface (SCI) is a newly established IEEE standard which provides bus-like services to a network of nodes connected by very fast, unidirectional links. SCI provides an efficient flow control protocol that fairly allocates bandwidth to all nodes on the network. When global fairness is not required, it is desirable to relax its enforcement, in exchange for increased network utilization. This paper presents an extension to SCI's fairness protocol that increases attainable throughput by enforcing fairness only among conflicting nodes. The authors present extensive simulation results and compare them to the standard SCI protocol and to the desired performance, which is derived in the paper. The comparisons show that, on average, the enhancements substantially increase the performance of the original protocol.>

High performance multiprocessing systems have been increasingly using heterogeneous digital signal processors (DSPs) for overall systems gain. Scheduling a DSP algorithm on such a system must address issues of interprocessor communication as well as parallelism extraction for optimal throughput. These issues have been extensively examined for multiprocessor systems incorporating homogeneous processors. A heterogeneous macropipelined scheduling scheme has been described which addresses the aforementioned communication and parallelization issues. The advantage of resorting to a heterogeneous scheme in specific cases is illustrated with examples.>