Browse Prior Art Database

OPTIMAL INSTRUCTION SCHEDULING FOR A CLASS OF VECTOR PROCESSORS: AN INTEGER PROGRAMMING APPROACH

IP.com Disclosure Number: IPCOM000128453D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Arya, Siamak: AUTHOR [+3]

Abstract

by Siamak Arya

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 55

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

OPTIMAL INSTRUCTION SCHEDULING FOR A CLASS OF VECTOR PROCESSORS: AN INTEGER PROGRAMMING APPROACH

Siamak Arya

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 CRL-TR-19-83

APRIL 1983

Room 1079, East Engineering Building Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

OPTIMAL INSTRUCTION SCHEDULING FOR A CLASS OF VECTOR PROCESSORS: AN INTEGER PROGRAMMING APPROACH by Siamak Arya

A Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer, Information, and Control Engineering) in The University of Michigan 1983

Doctoral Committee:

Professor Donald A. Calahan, Chairperson Assistant Professor John R. Birge
Assistant Professor Trevor N. Mudge Professor Norman R. Scott
Associate Professor Toby J. Teorey

ABSTRACT

by

Siamak Arya

An integer programming model that portrays the architectural features of a class of vector and array processors has been developed. This model is used to produce optimal schedules for low- level-instruction codes of such processors. Optimal schedules are produced for both straight codes and instruction loops. The model is extended to optimally reassign registers to instructions in addition to instruction sequencing. The model is further extended to consider processors with multiple identical functional units. A study of the complexity of the model shows that the scheduling time increases exponentially with the number of instructions. Using the model, a number of experiments have been conducted in optimal scheduling of Cray assembly codes. Siamak Arya 1983

1 Any opinion, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

University of Michigan Computing Research Laboratory Page 1 Apr 01, 1983

Page 2 of 55

OPTIMAL INSTRUCTION SCHEDULING FOR A CLASS OF VECTOR PROCESSORS: AN INTEGER PROGRAMMING

APPROACH

All Rights Reserved To my father, my mother,
Anna, Flooria, and Sohrab

ACKNOWLEDGEMENTS

I would like to take this opportunity to thank the members of my committee, my family, and my friends who have provided me with their time, ideas, and support during the course of this research.

I am especially grateful to Professor Donald A. Calahan for providing me with his friendship, guidance, encouragement, and inspiration. He always found the time to helpfully respond to my questions and problems.

I would like to express my appreciation to Professors Birge, Scott, Teorey, and Mudge for the care and wisdom they demonstrated during the supervision of this project. My special gratitude is extended to Professor James C. Bean with whom I have had many inspiring discussions.

My family has played a vital role in encouraging me to pursue a doctorate and in supporting me through out the process. I wish to express my warmest appreciation and love to them for their significant contributions to my p...