AN INTERACTIVE ALGORITHM DESIGN TOOL FOR EMBEDDED MULTIPROCESSOR SYSTEMS

THIS RESEARCH WILL ULTIMATELY PRODUCE AN INTERACTIVE ALGORITHM DESIGN TOOL FOR EMBEDDED MULTIPROCESSOR SYSTEMS. DESIGNERS WILL SPECIFY ALGORITHM STRUCTURE AS A DIRECTED GRAPH OF INTERCONNECTED NODES. THE TOOL AUTOMATICALLY PARTITIONS THESE GRAPHS INTO TASKS AND THEN ASSIGNS THESE TASKS TO PROCESSORS. THESE GROUPINGS AND ASSIGNMENTS WILL OPTIMIZE ALGORITHM PERFORMANCE (I.E., THROUGHPUT AND PROCESSING DELAYS) BASED ON THE TARGET MULTIPROCESSOR SYSTEM'S CHARACTERISTICS: DISTRIBUTED OPERATING SYSTEM, NETWORK TOPOLOGY AND HARDWARE. THE OPTIMIZED TASKS WILL BE TRANSLATED INTO AN ADA TEMPLATE TO SUPPORT ALGORITHM IMPLEMENTATION ON A TARGET MULTIPROCESSOR SYSTEM. THE INNOVATION IN THIS RESEARCH IS THE UNIQUE COMBINATION AND INTEGRATION OF GRAPHICS, OPTIMIZATION, ALGORITHM EVALUATION,AND CODE GENERATION TECHNOLOGIES WHICH EFFECTIVELY DECOUPLE ALGORITHM FUNCTIONALITY AND COMPUTATIONAL COMPLEXITY ISSUES FROM IMPLEMENTATION LEVEL PERFORMANCE DECISIONS. BY AUTOMATING MUCH OF THE DESIGN PROCESS, PRODUCING OPTIMAL GRAPHS, AND ENSURING THAT THE CODE IS TRACEABLE TO THE DESIGN, THE SOFTWARE DEVELOPMENT PROCESS WILL BE LESS COSTLY, MORE TIMELY, AND MORE RELIABLE. THREE TECHNICAL OBJECTIVES WILL DEMONSTRATE THE TECHNICAL FEASIBILITY OF THE INTERACTIVE ALGORITHM DESIGN TOOL: (1) DEVELOP A GRAPHICAL ALGORITHM SPECIFICATION LANGUAGE, (2) DEVISE A TECHNIQUE TO GENERATE TARGET OPTIMAL IMPLEMENTATIONS OF PARALLEL ALGORITHMS, AND (3) DESIGN AN AUTOMATIC TECHNIQUE TO TRANSLATE OPTIMIZED GRAPHS INTO ADA CODE TEMPLATES.