Studies on methods of reducing some cost parameters in microprogrammed digital computers and distributed processing systems

Abstract

The concept of microprogramming is frequently employed in designing the control units of modern digital computers and microprocessors. In a microprogrammed digital computer, the size of control memory depends upon the width (in bits) of the microinstruction word. An optimum microinstruction format reduces the width and hence the cost of the control memory to the extent that parallelism in microoperations is not lost. Recent advances in LSI technology have resulted in low-cost mini and microprocessors which can be configured into a distributed processing system. A distributed processing system has the advantages of high speed, modular expandability, and reliability. An efficient task allocation algorithm distributes modules of a task to various processors economically such that their loads are balanced and the communication between modules is kept minimum. Such an algorithm has a direct effect on the cost of implementing jobs in a distributed processing system. The purpose of this thesis is to develop methods of reducing the cost of implementing microprograms at the individual processor level, and to develop a cost-effective strategy of task allocation when several processors are employed. The width optimization of control memory is so far handled mostly in switching theoretic approach whereas the task allocation is handled either in a heuristic manner or by employing mathematical programming techniques. For reducing the word-width of a control memory microinstruction, this thesis deals with the development of a simple and systematic approach. The method requires the computation of maximal compatibility classes of only a subset of microoperations, unlike the existing methods in which the entire set of microoperations is used. The main emphasis in this method is to obtain a good engineering solution with a reduced computational effort. The task allocation problem is tackled by a new clustering and covering approach that yields a minimum interprocessor communication cost under a specified load balancing constraint. In this method, all possible module clusters that satisfy the load balancing constraint are first derived, starting from a set of module pairs that give maximum saving in interprocessor communication cost. Out of all possible covers which can be formed from these clusters, the cover that closely fits into the application environment is then chosen for making the allocation. Exhaustive enumeration of all clusters is avoided by recognizing certain special properties of the modules and clusters. The algorithm is flexible and generates a solution in every case including tree-like module configurations. The solution generated is independent of the starting value of the load balancing constraint and saves a considerable amount of computational effort.