Bounding the Number of Processors and Checkpoints Needed in Time-minimal Parallel Reversal Schedules

摘要: For derivative calculations, debugging, and interactive control one may need to reverse the execution of a computer program for given inputs. If any increase time needed reversal is unacceptable, availability enough auxiliary processors provides possibility with minimal temporal complexity surprisingly small spatial using parallel schedules. This paper describes structure such schedules that use checkpointing technique on multi-processor machine. They are shown require least number memory locations store checkpoints certain steps.