Article Preview
TopMotivation And Introduction
Multi-Processor Systems-on-Chip (MPSoCs) are nowadays widely used because of their high performance and power efficiency. Representative examples are TI OMAP processors (Texas Instruments, Inc., 2013), Qualcomm Snapdragon processors (Qualcomm, Inc., 2013) and the ARM MPCore technology (ARM Ltd., 2013). In MPSoCs, applications are typically partitioned into tasks for parallel execution on different processing elements (PEs). To protect shared resources like memories or I/O peripherals and to prevent data corruption, mutual exclusion needs to be guaranteed. Spinlocks are widely used to ensure that a shared resource can only be accessed by one task at a time.
In literature, many studies have been carried out on the implementation of spinlocks. Most of them focus on the fairness of spinlock acquisition or the reduction of transaction costs due to repeatedly requesting the locks. However, they typically do not consider application knowledge. This leads to a random acquisition order of spinlocks. In many cases, this results in a low parallelism in task execution, and consequently worsens the system performance. A simple example is depicted in Figure 1, in which two PEs compete for the same spinlock. In the example, two different execution sequences of tasks are possible by acquiring the lock in different orders. The execution time shows that assigning the spinlock to PE2 first (Figure 1(b)) is a better choice, which achieves a higher performance.
Figure 1. Impact of spinlock acquisition order
Despite its simplicity, this example shows that a smart control of spinlocks can increase the system performance. To guide the spinlock control in a smart way, application knowledge such as task sizes and task dependencies needs to be considered.
In this work, experiments are done by including application knowledge into the spinlock control flow. As the application knowledge varies from one application to another, it is important to have user-defined spinlock control algorithms, which can be adapted to the application. Instead of developing yet another control unit in the system to execute user-defined algorithms, which will introduce high area cost, they can naturally be implemented on an existing system controller. However, the controller should be programmable, can e.g. be a RISC processor or an Application-Specific Instruction-set Processor (ASIP). This work uses systems with an ASIP controller as the experiment platforms. This ASIP is called OSIP, which stands for Operating System ASIP and was originally designed for task scheduling and mapping.
The remainder of this paper is organized as follows. After discussing about the related work, a brief overview of OSIP-based MPSoCs is given. Next, an application-aware spinlock control flow in OSIP-based systems is introduced, which starts from the high-level integration of application knowledge down to the low-level realization. Two case studies – a synthetic application and a multimedia application (H.264 video decoding) are performed, which demonstrate the efficiency of the proposed spinlock control mechanism and highlight the advantages of using an ASIP as the system controller. Finally, a summary and an outlook are given.
TopA commonly used technique to address mutual exclusion in multi-processor systems is to use spinlocks. Many implementations have been proposed for spinlocks in literature. The simplest approach is the test-and-set lock, which repeatedly tries to replace the lock flag with true in order to acquire the lock. Although the implementation is rather simple, it introduces heavy traffic load due to continuous updates of the flag, especially in cache coherent systems. One improvement is suggested by using the test and test-and-set lock (Rudolph & Segall, 1984), in which updates are only made when the lock is assumed to be available. Another important improvement is introduced by Anderson (1990) by adding a certain delay (backoff) between two unsuccessful trials.