vm@etf.rs

• Microprocessor systems on a chip
• Cache and cache hierarchy
• Instruction level parallelism
• Branch prediction strategies
• Input/output bottleneck
• Multithreaded processing
• Shared memory multiprocessor systems
• Distributed shared memory systems

vm@etf.rs

Design of microprocessor and/or multimicroprocessor systems represents a continuous struggle; success (if achieved) lasts only infinitesimally long and disappears forever, unless a new struggle (with unpredictable results) starts immediately. In other words, it is a continuous survival process, which is the main motto of this book.

This book is about survival of those who have contributed to the state of the art in the rapidly changing field of microprocessing and multimicroprocessing on a single chip, and about the concepts that have to find their way into the next generation microprocessors and multimicroprocessors on a chip, in order to enable these products to stay on the competitive edge.

This book is also about the microprocessor and multimicroprocessor based designs of the author himself, and about the lessons that he has learned through his own professional survival process which lasts for about two decades now; concepts from microprocessor and multimicroprocessor boards of the past represent potential solutions for the microprocessor and multimicroprocessor chips of the future.

In this book, the issues of importance for current on-board microprocessor and multimicroprocessor based designs, as well as for future on-chip microprocessor and multimicroprocessor designs, have been divided into ten different topics. Each of the topics is further subdivided into three different sections:

1. the first one on the basics (traditional body of knowledge),
2. the second one on the advances (state of the art information), and
3. the third one on the efforts of the author and his associates (a brief research report).

After long discussions with more experienced colleagues (see the list in the acknowledgment section), and the more enthusiastic students (their wishes should represent the highest priority), the ten major topics have been selected, as follows:

1. Microprocessor systems on a chip
2. Cache and cache hierarchy
3. Instruction level parallelism
4. Branch prediction strategies
5. Input/output bottleneck
6. Multithreaded processing
7. Shared memory multiprocessing systems
8. Distributed shared memory systems
9. Multicomputer systems
10. Distributed computer systems

Topics related to issues in uniprocessing are of importance for microprocessor based designs of today and the microprocessor on-chip designs of immediate future. Topics related to multiprocessing are of importance for multimicroprocessor based designs of today and the multimicroprocessor on-chip designs of the not so immediate future. The author is one of the believers in the prediction that future on-chip machines, even if not of the multimicroprocessor or multicomputer type, will include strong support for multiprocessing and multicomputing. Consequently, as far as multiprocessing and multicomputing is concerned, only the issues of importance for future on-chip machines have been selected.

This book also includes a prolog section, which explains the roots of the idea behind it: combining synergistically the general body of knowledge and the particular experiences of an individual who has survived several pioneering design efforts of which some were relatively successful commercially.

Finally, this book also includes an epilog section, with three case studies, on three microprocessor based designs involving multiple microprocessors. The author was deeply engaged in all three designs. In this author’s opinion, each project, in the field which is the subject of this book, includes three major types of activities:

1. envisioning of the strategy
   (project directions and milestones),
2. consulting on the tactics
   (product architecture and organization), and
3. engaging in the battle
   (design and almost exhaustive testing on all logical levels, until the product is ready for the market).

The first case study is on a multimicroprocessor implementation of a data modem for high frequency radio. This design has been often quoted as the world’s first multimicroprocessor based high frequency data modem. The work was done in 70s; however, the interest in the results reincarnated both in 80s (due to technology impacts which enabled miniaturization) and in 90s (due to application impacts of wireless communications). The author, absolutely alone, took all three roles defined above (one technician only helped with wire-wrapping, using the list prepared by the author), and brought the product to a market success (after the wire-wrap boards were turned, by others, into the printed-circuit boards) in less than two years (possible only with the enthusiasm of a novice). See the reference in the acknowledgment section, as a pointer to details (this reference is not the earliest one, but the one which conveys most information of interest for this book).

The second case study is on a multimicroprocessor implementation of a GaAs systolic array for Gram-Schmidt orthogonalization (GSO). This design has been often quoted as the world’s first GaAs systolic array. The work was done in 80s; the interest in the results did not reincarnate in 90s. The author took only the first two roles; the third one was taken by the others (see the acknowledgment section), but never really completed, since the project was canceled before its full completion, due to enormous cost (total of 8192 microprocessor nodes, each one running at the speed of 200 MHz). See the reference in the acknowledgment section, as a pointer to details (this reference is not the earliest one, but the one which conveys most information of interest for this book).

The third case study is on the implementation of a board (and the preceding research) which enables a personal computer (PC) to become a node in distributed shared memory (DSM) systems of the reflective memory system (RMS) type. This design has been often quoted as the world’s first DSM plug-in board for PC technology (some efforts with larger visibility came later; one of them, with probably the highest visibility, as an indirect consequence of this one). The work was done in 90s. The author took only the first role and was responsible for the project (details were taken care of by his graduate students); fortunately, the project was completed successfully (and which is more important for a professor, papers were published with timestamps prior to those of the competition). See the reference in the acknowledgment section, as a pointer to details (this reference is not the earliest one, but the one which conveys most information of interest for this book).

All three case studies have been specified with enough details, so the interested readers (typically undergraduate students) can redesign the same product using a state of the art technology. Throughout the book, the concepts/ideas and lessons/experiences are in the foreground; the technology characteristics and implementation details are in the background, and can be changed by the reader, if so desired. This book:

is nicely complemented with other books of the same author, by the same publisher. One of them is:

The above two books together (in various forms) have been used for about a decade now, by the author himself, as textbooks for two undergraduate courses that he has taught periodically at various universities worldwide. Other books are on the more advanced topics, and have been used in graduate teaching on the follow up subjects:

In conclusion, his book covers only the issues which are, in the opinion of the author, of strong interest for future design of microprocessors and multimicroprocessors on the chip. These issues have been treated selectively, with more attention paid to topics which are believed to be of more importance. This explains the difference in the breath and depth of coverage throughout the book.

Also, the selected issues have been treated with a various level of detail. This was done intentionally, in order to create room for creativeness of the students. Typical homework requires that the missing details be completed, and the inventiveness with which the students fulfill the requirement is sometimes unbelievable (the best student projects can be found on the author’s coursework web page). Consequently, one of the major educational goals of this book, if not the major one, is to help create the inventiveness among the students. Suggestions on how to achieve this goal more efficiently are more than welcome.

Finally, a few words on the educational approach used in this book. It is well known that “one picture is worth of one thousand words.” Consequently, the stress in this book has been placed on figures and figure captions. All necessary explanations have been put into the figures and figure captions. The main body of the text has been kept to its minimum—only the issues of interest for the global understanding of the topic and/or the thoughts on experiences gained and lessons learned. Consequently, students claim that this book is fast to read and easy to comprehend.

• The worls’s first multimicroprocessor HF modem:
  MISD for DFT (70s).
• The world’s first GaAs systolic array:
  SISD for GSO (80s).
• The world’s first DSM for personal computers:
  MIMD for RMS (90s).

• Survival
• Synergy
• Success

• Academia
• Industry
• Family

[Milutinovic80] Milutinovic, V.,
“One Approach to Multimicroprocessor Implementation of Modem
for Data Transmission over HF Radio,”
Proceedings of EUROMICRO-80,
London, England, Europe, September 1980, pp. 107–111.

[Fortes86] Fortes, J., Milutinovic, V., Dock, R., Helbig, W., Moyers, W.,
“A High-Level Systolic Architecture for GaAs,”
Proceedings of the HICSS-86,
Honolulu, Hawaii, USA, January 1986, pp. 253–258.

[Savic95] Savic, S., Tomasevic, M., Milutinovic, V., Gupta, A., Natale, M., Gertner, I.,
“Improved RMS for the PC Environment,”
Microprocessors and Microsystems,
Vol. 19, No. 10, December 1995, pp. 609–619.

This book would not be possible without the help of numerous individuals; some of them helped the author to master the knowledge and to gather the experiences necessary to write this book; others have helped to create the structure or to improve the details. Since the book of this sort would not be possible if the author did not take place in the three large projects defined in the preface, the acknowledgment will start from those involved in the same projects, directly or indirectly.

In relation to the first project (MISD for DFT), the author is thankful to professor Georgije Lukatela from whom he has learned a lot, and also to his industrial colleagues who worked on the similar problems in the same or other companies (Radenko Paunovic, Slobodan Nedic, Milenko Ostojic, David Monsen, Philip Leifer, and John Harris).

In relation to the second project (SIMD for GSO), the author is thankful to professor Jose Fortes who had an important role in the project, and also to his industrial colleagues who were involved with the project in the same team or within the sponsor team (David Fura, Gihjung Jung, Salim Lakhani, Ronald Andrews, Wayne Moyers, and Walter Helbig).

In relation to the third project (MIMD for RMS), the author is thankful to professor Milo Tomasevic who has contributed significantly, and also to the colleagues who were involved in the same project, within his own team or within the sponsor team (Savo Savic, Milan Jovanovic, Jelica Protic, Ziya Aral, Ilya Gertner, and Mark Natale).

The list of colleagues professors who have helped about the overall structure and contents of the book, through formal or informal discussions, and direct or indirect advice, on one or more elements of the book, during the seminars presented at their universities or during the friendly chatting between conference sessions, or have influenced the author in other ways, includes but is not limited to the following individuals: Michael Flynn, John Hennessy, Anoop Gupta, Jack Dennis, Yale Patt, Trevor Mudge, Alan Smith, Kai Hwang, Jean-Luc Gaudiot, H.J. Siegel, Hank Dietz, Richard Schwartz, Kai Li, Liviu Iftode, Daniel Tabak, Borko Furht, Bozidar Levi, Milos Ercegovac, Vojin Oklobdzija, Srdjan Mitrovic, Branislava Perunicic, Antonio Prete, Mateo Valero, Jacques Tiberghien, Tihomir Aleksic, Jozo Dujmovic, Dusan Velasevic, Borivoj Lazic, Jovan Djordjevic, Zoran Jovanovic, Igor Tartalja, Emil Jovanov, Jasna Ristic, Dejan Zivkovic, Milutin Ostojic, Ljubisa Stankovic, Vidojko Ciric, Dusan Starcevic, and Bozidar Radenkovic.

The list also includes numerous individuals from industry worldwide who have provided support or have helped clarify details on a number of issues of importance: Djordje Rosic, Charles Rose, Maurice Wilkes, Lee Hoevel, Oleg Panfilov, Hans Hilbrink, Helmut Weber, Charles Gimarc, Tom Brumett, Gad Sheaffer, Mark Tremblay, and Roger Denton.

Students have helped a lot to maximize the overall educational quality of the book. Several generations of students have used the book before it went to press. Their comments and suggestions were of extreme value. Those who deserve special credit are: Aleksandar Milenkovic, Goran Davidovic, and Vladan Dugaric. Also, Zvezdan Petkovic, Dejan Raskovic, Boris Markovic, Jovanka Ciric, Aleksandra Grujic, and Milena Petrovic.

Finally, the role of the family was crucial. Wife Dragana took on the management of teenagers (Dusan, Milan, Goran) so the father can write the book; she also has read carefully the most critical parts of the book, and has helped improve the wording. Father Milan, mother Simonida, and uncle Ratoljub have helped with their life experiences.