Run-time mechanisms for fine-grained parallelism on network processors: The TILEPro64 experience

The efficient parallelization of very fine-grained computations is an old problem still challenging also on modern shared memory architectures. Scalable parallelizations are possible if the base mechanisms provided by the run-time support (for inter-thread/inter-process synchronization/communication) are carefully designed and developed on top of parallel architectures. This requires a deep knowledge of the hardware behavior and the interaction patterns used by the parallelism paradigms. In this paper we present our experience in developing efficient inter-thread interaction mechanisms on the Tilera TILEPro64 network processor. Although it is a domain-specific parallel architecture, the TILEPro64 represents a notable example of how advanced architectural structures, such as user-accessible on-chip interconnection networks and configurable cache coherence protocols, are of great importance to design lightweight cooperation mechanisms enabling efficient parallel implementations of fine-grained problems. The paper presents our ideas and an experimental evaluation that compares our proposals with other existing run-time supports.