Research Initiation Program - Classifying Shared Objects by their Synchronization Power

这个项目的主要目标是获得并行处理系统中同步原语的分类，其目标是反映每个原语的功能和局限性。并行处理系统解决计算问题的有效性在很大程度上取决于对进程间通信和同步的支持。在共享内存系统中，更高级的共享对象（如共享队列）在软件中使用共享硬件原语（如寄存器和test&amp；set指令）实现。在容错异步系统中，进程以任意变化的速率进行，这样的软件实现必须保证一个进程能够成功完成，而不管其他进程有多快或多慢。众所周知，硬件原语支持这类软件实现的能力差别很大。本研究提出的分类将揭示同步原语的能力和局限性。这种分类对于多处理器设计者决定在硬件中支持哪种原语是很有用的。对于系统程序员来说，它在确定一个高级对象（例如，一个可以被100个进程同时访问的队列）在给定系统中是否具有软件实现方面也很有用。＊＊＊

9410421 Jayanti The main objective of this project is to obtain a classification of synchronization primitives in parallel processing systems, with the goal of reflecting the power and limitations of each primitive. The effectiveness of a parallel processing system to solve a computation depends to a large extent on the support for communication and synchronization among processes. In shared memory systems, higher level shared objects such as shared queues are implemented in software using shared hardware primitives like registers and test&set instructions. In fault- tolerant asynchronous systems, where processes progress at arbitrarily varying rates, such software implementations must guarantee that a process can complete successfully, regardless of how fast or slow the other processes are. It is known that hardware primitives vary widely in their ability to support such software implementations. The classification proposed in this research will bring out the capabilities and limitations of synchronization primitives. The classification will be useful to the designer of a multiprocessor in deciding which primitive to support in hardware. It will also be useful to the systems programmer in determining whether a high level object of interest (e.g., a queue that can be accessed concurrently by 100 processes) has a software implementation in a given system. ***