The Shadow Algorithm: A Scheduling Technique for Both Compiled and Interpreted Simulation

Abstract

The shadow algorithm is an event-driven unit-delay simulation technique that has been designed to take advantage of the instruction caches present in many of the latest workstations. The algorithm is based on the threaded-code technique, but uses a dynamically created linked list of environments called shadows. Compiled shadow algorithm simulations run in about 1/5th the time required for a conventional interpreted event-driven simulation. The interpreted shadow algorithm runs in about 1/4th the time of a conventional interpretive simulation.