OPTIMISTIC SCHEDULING OF NON-NUMERIC TASKS ON HIGHLY PARALLEL PROCESSOR ARCHITECTURES

OBJECTIVE: TO DEVELOP IMPROVED TECHNIQUES AND ALGORITHMS FOR THE OPTIMISTIC EXECUTION OF LARGE-SCALE SYMBOLIC COMPUTATIONS ON HIGHLY PARALLEL MULTIPROCESSORS. PHASE I WILL EXPLORE THE FEASIBILITY OF AUTOMATICALLY SCHEDULING MANDATORY AND SPECULATIVE TASKS USING INFORMATION GAINED FROM BOTH COMPILE-TIME AND CONCURRENT RUN-TIME STRICTNESS ANALYSES, WHICH PERFORM CONCURRENT MEANS-END ANALYSES ON TASKS. WE WILL ALSO INVESTIGATE THE AUTOMATIC BUILDING OF CONCURRENTLY RUNNING RESOURCE CONSUMPTION MODELS, WHICH CAN PROVIDE EVEN MORE INFORMATION ABOUT THE TIME AND SPACE REQUIREMENTS OF SUB-TASKS. THE TECHNIQUEES AND ALGORITHMS DEVELOPED IN PHASE II CAN BE EXTENDED, PROTOTYPED AND MEASURED ON A MIMD PROCESSOR IN PHASE II. A SUCCESSFUL PROJECT CAN PROVIDE DRAMATIC PERFORMANCE GAINS IN MANY PARALLEL SYMBOLIC COMPUTATIONS, AS A RESULT OF SHORTER TIME-TO-RESULT DUE TO IMPROVED SCHEDULING.