Article Preview
Top1. Introduction
Shared-memory multiprocessors are commonplace in current computers, and multi-core processor chips are used not only in high-end servers but also in desktop and portable computers, even embedded ones. To benefit from core multiplicity, application programmers have to write parallel programs. They need to expose the inherent parallelism in an algorithm and express it explicitly, for example, by using a multithreading library.
Many techniques for parallelizing sequentially-coded programs have been developed (Zima, 1990). Most of them analyze the dependencies among iterations of a loop in a program and execute iterations only if it is assured that they have no dependencies on each other. In some simple cases, a compiler can automatically generate excellent codes executing a loop in parallel. However, when there are inter-iteration dependencies only in a small subset of iterations and other iterations have no dependency on each other, no compiler can parallelize the loop. To parallelize such loops, we proposed a concept called speculative memory (SM) (Hirata, 2016).
Conventionally, speculative execution (Kaeli, 2005; Hirata, 1992; Akkary, 1998; Marcuello, 1999; Hammond, 2000; Vijaykumar, 2001; Steffan, 2005; Ohsawa, 2005; Hertzberg, 2011; Odaira, 2014; Shoji, 2016) of a small segment in a program is provided mainly by hardware mechanisms—with the partial support of compilers—and is invisible to programmers. But with SM, programmers can specify the speculative execution of loop iterations explicitly in their programs. The SM system creates a thread to execute an iteration of a loop. The results of the execution of the thread are committed if the thread does not violate the dependency on other threads executing earlier iterations. If it does, the SM system forces it to abort and re-start the execution of the iteration. With this aborting capability, SM does not always require the assurance that the loop is parallelizable. Consequently, SM gives programmers more opportunities to extract the parallelism of their programs.