摘要： The goal of this work is to facilitate efficient use of concurrent shared objects in asynchronous, shared-memory multiprocessors. Shared objects are usually implemented using locks in such systems. However, lock-based implementations result in substantial inefficiency in multiprogrammed systems, where processes are frequently subject to delays due to preemption. This inef ciency arises because processes can be delayed while holding a lock, thereby delaying other processes that require the lock. In contrast, lock-free and wait-free implementations guarantee that the delay of one process will not delay another process. We show that lock-free and wait-free imple- mentations for shared objects provide a viable alternative to lock-based ones, and that they can provide a signi cant performance advantage over lock-based implementations in multiprogrammed systems. Lock-free and wait-free implementations are notoriously difficult to design and to verify as correct. Universal constructions alleviate this problem by generating lock-free and wait-free shared object implementations using sequential implementations. However, previous universal constructions either require signi cant creative effort on the part of the programmer for each object, or result in objects that have high space and time overhead due to excessive copying. We present lock-free and wait-free universal constructions that achieve low space and time overhead for a wide spectrum of important objects, while not placing any extra burden on the object programmer. We also show that the space and time overhead of these constructions can be further reduced by using k-exclusion algorithms to restrict access to the shared object. This approach requires a long-lived renaming algorithm that enables processes to acquire and release names repeatedly. We present several efficient k-exclusion and long-lived renaming algorithms. Our universal constructions are based on the load-linked and store-conditional synchronization inst

摘要： The key issues in the design of Systems-on-Chip (SoC) are eciency, design cost and time to market. To deal with the trade-o between them, the idea of component standardization has been adopted. In Philips Research, a design team is working on a standard multi- processor interface called Task Transaction Layer (TTL). TTL is basically an application programming interface (API) that allows the Intellectual-property (IP) blocks to interact with each other in a uniform way such that the design of the system functionality can be separated from the design of architecture and the two parts can still be easily integrated in a plug-and-play fashion. The initial fo- cus is on streaming-based multimedia processing embedded systems. During the TTL design phase, dierent design choices on inter-task communication have been proposed. The main task of this thesis is to evaluate those design choices in the aspect of ease of programming in a quantitative way. To achieve this, a top-bottom design method- ology: Y-chart, typical multimedia processing applications and the proposals of TTL are studied, an evaluation method is proposed and applied on the comparison of TTL design choices. The result can be used as a reference in TTL design choice making as well as a guide in TTL application design.

摘要： Recent increases in hard fault rates in modern chip multi-processors have led to a variety of approaches to try and save manufacturing yield. Among these are: fine-grain fault tolerance (such as error correction coding, redundant cache lines, and redundant functional units), and large-grain fault tolerance (such as disabling of faulty cores, adding extra cores, and core salvaging techniques). This paper considers the case of core salvaging techniques and the heterogeneous per- formance introduced when these techniques have some salvaged and some non-faulty cores. It proposes a hypervisor-based hardware thread scheduler, triggered by detection of spin locks and thread imbalance, that mitigates the loss of throughput resulting from this het- erogeneity. Specifically, a new algorithm, called Most Progress Made algorithm, reduces the number of synchronization locks held on a salvaged core and balances the time each thread in an application spends running on that core. For some benchmarks, the results show as much as a 2.68x increase in performance over a salvaged chip multi-processor without this technique.