The spring scheduling coprocessor is a novel very large scale integration (VLSI) accelerator for multiprocessor real-time systems. The coprocessor can be used for static as well as online scheduling. Many different policies and their combinations can be used (e.g., earliest deadline first, highest value first, or resource-oriented policies such as earliest available time first). In this paper, we describe a coprocessor architecture, a CMOS implementation, an implementation of the host/coprocessor interface and a study of the overall performance improvement. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude. We also present an overall system improvement analysis by accounting for the operating system overheads and identify the next set of bottlenecks to improve. The scheduling coprocessor includes several novel VLSI features. It is implemented as a parallel architecture for scheduling that is parameterized for different numbers of tasks, numbers of resources, and internal wordlengths. The architecture was implemented using a single-phase clocking style in several novel ways. The 328 000 transistor custom 2-/spl mu/m VLSI accelerator running with a 100-MHz clock, combined with careful hardware/software co-design results in a considerable performance improvement, thus removing a major bottleneck in real-time systems.

The design of a kernel-level thread package for dynamic, hard real-time environments is presented. A highly integrated design is used to ensure predictability. A system description language and real-time programming language are used to specify key properties of threads and thread groups. For a thread, this includes whether or not the thread spawns other threads at run-time, the type of performance guarantee the thread requires, how the thread interacts with other threads, and what processors the thread may execute on. A predictable kernel uses this information along with on-line dynamic guarantees to ensure predictable execution of threads. The first phase of the thread package has been implemented and performance measurements have indicated a 66% improvement in context switching costs.

We present a novel co-processor for multiprocessor scheduling in the Spring real-time operating system. Since most dynamic scheduling problems are NP-complete, we use a heuristic algorithm which uses a smart searching scheme to find a feasible schedule for a set of specified tasks and hard deadlines. A parallel VLSI architecture for scheduling is developed that can be scaled for different numbers of tasks, numbers of resources, internal wordlengths, and future IC technologies. The scheduling architecture is implemented in a 0.8/spl mu/ CMOS technology and uses an advanced clocking scheme to allow further scaling to future technologies. With an internal clock rate of 100 MHz, a speed increase of two orders of magnitude is expected for scheduling tasks, thus removing a major bottleneck in real-time systems.>

We present a novel VLSI co-processor for real-time multiprocessor scheduling. The co-processor can be used for sophisticated static scheduling as well as for online scheduling using many different algorithms such as earliest deadline first, highest value first, or the Spring scheduling algorithm. When such an algorithm is used online it is important to assess the performance impact of the interface of the co-processor to the host system, in this case, the Spring kernel. We focus on the interface and its implications for overall scheduling performance. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude and speeds up the overall scheduling operation 30 fold. The parallel VLSI architecture for scheduling is briefly presented. This architecture can be scaled for different numbers of tasks, resources, and internal word lengths. The implementation uses an advanced clocking scheme to allow further scaling using future IC technologies.>