Compile-Time Charactirization Recurrent Patterns in Irregular Computations

Many engineering applications use irregular array access functions. Compile-time characterization of the computation structure of such applications is infeasible, making the automatic generation of efficient communication dificuit. This paper considers the Inspector-Executor (IEJ compilalion model to handle such applications. In this model, a run-time inspection of the computation is followed by the aciual execution. This paper discusses the assue of automatic compile-time identification of sections of a program that have recurrent computational patterns so that the cost of run-time inspection is amortizable over many executions. An algorithm is presented and an illusiraitve example is given.