MELD SCHEDULING - A TECHNIQUE FOR RELAXING SCHEDULING CONSTRAINTS

Meld scheduling melds the schedules of neighboring scheduling regions to respect latencies of operations issued in one region but completing after control transfers to the other. In contrast, conventional sched ulers ignore latency constraints from other regions leading to potenti ally avoidable stalls in an interlocked (superscalar) machine or incor rect schedules for noninterlocked (VLIW) machines. Alternatively, sche dulers that conservatively require all operations to complete before t he branch takes effect produce inefficient schedules. In this paper, w e present general data structures for maintaining latency constraint i nformation at region boundaries. We present a meld scheduling algorith m for noninterlocked processors that generates latency constraints at the boundaries of scheduled regions and utilizes this information duri ng the scheduling of other regions. We present a range of design optio ns and describe the reasons behind our particular choices. We evaluate the performance of meld scheduling an a range of machine models on a set of SPEC92 and UNIX benchmarks.