Browse Prior Art Database

AN ALGORITHM TO DESIGN THE MEMORY CONFIGURATION 01? A COMPUTER NETWORK

IP.com Disclosure Number: IPCOM000127999D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 20 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

Dennis Rafura: AUTHOR [+4]

Abstract

The study of abstract models of computer systems using deterministic methods has produced significant insight into the behavior of such systems in recent years. This paper considers a model of a minicomputer network which consists of an arbitrary number of identical processors. Each processor in the network has a fixed; though possibly different sized, private memory. The network processes a set of tasks with known execution times and memory requirements. One of the problems a designer of such a network must solve is to determine the memory size for each processor. It is desirable to keep the total amount of memory used small and the processors highly utilized during the processing of the set of tasks. This paper presents an algorithm to determine the memory sizes for such a system. Under a given scheduling strategy, E the processor utilization and the total memory used are analyzed using worst- . case bounds and simulation studies. The proposed algorithm is shown to be better than two other simple methods to determine the memory sizes.

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

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN ALGORITHM TO DESIGN THE MEMORY CONFIGURATION 01? A COMPUTER NETWORK

by

Dennis Rafura V. Y. Shen

Technical Report # 76-6 March, 1976

AN ALGORITHM TO DESIGN THE MEMORY CONFIGURATION OF A COMPUTER NETWORK

D, G . Ka.fura V . Y, . Shen Computer Science Department Computer Science Department Iowa State University Purdue University Amen, Iowa 50011 West.Lafayette, Indiana 47904

KEYWORDS: deterministic models, design algorithms, system configuration, computer networks, multiprocessor systems CR categories: 4.32, 5.39

Abstract

The study of abstract models of computer systems using deterministic methods has produced significant insight into the behavior of such systems in recent years. This paper considers a model of a minicomputer network which consists of an arbitrary number of identical processors. Each processor in the network has a fixed; though possibly different sized, private memory. The network processes a set of tasks with known execution times and memory requirements. One of the problems a designer of such a network must solve is to determine the memory size for each processor. It is desirable to keep the total amount of memory used small and the processors highly utilized during the processing of the set of tasks. This paper presents an algorithm to determine the memory sizes for such a system. Under a given scheduling strategy, E the processor utilization and the total memory used are analyzed using worst- . case bounds and simulation studies. The proposed algorithm is shown to be better than two other simple methods to determine the memory sizes.

I. Introduction

Analysis of abstract models using deterministic methods has produced significant insight into the behavior of multiprocessor systems. The performance of scheduling strategies has been studied for models with a single (processor) resource [1-8] and also for systems with two (processor and memory) or more limited resources [9-15]. In these investigations the resources are assumed fixed while the scheduling strategy may be changed and the workload (task set) is arbitrarily chosen. This approach represents the attempt to improve the performance of an existing system by changing its resource management. This paper presents an inverse problem in which the workload and the scheduling strategy are fixed and the resources are to be determined. This approach repre-sents the problem of designing a configuration to process a measured workload. The model presented in this paper consists of several identical and inde- pendent processors, each possessing a fixed, though possibly different sized, memory. Each processor can only execute one task at a time. A task requires some fixed amount of memory

Iowa State University Page 1 Dec 31, 1976

Page 2 of 20

AN ALGORITHM TO DESIGN THE MEMORY CONFIGURATION 01? A COMPUTER NETWORK

during its time of execution. It can be appreciated that the choice of memory size for each proce...