Three principles of optimality for multiprogramming derived from a general model of virtual memory computer system are presented. They state the existence of both an optimal multiprogramming degree and an optimal prog...
详细信息
Three principles of optimality for multiprogramming derived from a general model of virtual memory computer system are presented. They state the existence of both an optimal multiprogramming degree and an optimal program mixture in the multiprogramming set. The implementation of these principles is studied in a simulation model which permits, in contrast to analytical models, to relax assumptions on the workload submitted to the system. An appropriate dynamic control of the system is needed in order to achieve optimal performance. Proposed optimization takes into account such criteria as deadlines and priorities which are not directly related to system performance. The different results obtained on the system performance improvement are presented.
Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limite...
详细信息
Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limited number of processes fail is of particular interest.
A multiprocessing system composed of identical units is considered. This system is executing a set of partially ordered tasks, with known execution times, using a non-preemptive scheduling strategy. Lower bounds on th...
详细信息
A multiprocessing system composed of identical units is considered. This system is executing a set of partially ordered tasks, with known execution times, using a non-preemptive scheduling strategy. Lower bounds on the number of processors required to compute the tasks before a deadline, and on the minimum time to execute the tasks with a fixed number of processors, are of great value for the determination of the corresponding optimal schedules. In this paper, methods for the efficient computation of the lower bounds obtained by Fernández and Bussell are discussed. Computational improvements for the case of general partial orders are reported, and further reductions of the number of operations are shown to be possible for special graphs (trees, independent chains, independent tasks).
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the trans...
详细信息
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the transformations improve programs with respect to the measure. We show that it is possible to compute limits of infinite sequences of the transformations; this allows our system to implement software pipelining, and leads to a general solution to the problem of software pipelining in the presence of tests. Using the primitive transformations and the limit-taking transformation, it is possible to express the classical parallelization techniques for vector, multiprocessor, and VLIW machines. Thus, our transformational system can be viewed as a formal foundation for the area of parallelization. We present implementations of two techniques, doacross and a simple form of vectorization.
This paper presents a method of implementing the logic of a decision table in a computer program which is simpler and more efficient than a program derived from the rule-mask method. The method, based on decoding the ...
详细信息
This paper presents a method of implementing the logic of a decision table in a computer program which is simpler and more efficient than a program derived from the rule-mask method. The method, based on decoding the condition body entries to a mixed base, incorporate techniques for making certain entries in the decision table more specific, and enables the logic of the table and the validity of any stated set of condition entries to be checked more easily.
An algorithm is described that allows log(n) processors to sort n records in just over 2n write cycles, together with suitable hardware to support the algorithm. The algorithm is a parallel version of the straight mer...
详细信息
An algorithm is described that allows log(n) processors to sort n records in just over 2n write cycles, together with suitable hardware to support the algorithm. The algorithm is a parallel version of the straight merge sort. The passes of the merge sort are run overlapped, with each pass supported by a separate processor. The intermediate files of a serial merge sort are replaced by first-in first-out queues. The processors and queues may be implemented in conventional solid logic technology or in bubble technology. A hybrid technology is also appropriate.
National Software Works (NSW) is a DOD research and development effort designed to provide a software programming environment through the use of computer netting. While there are a number of software technical and man...
详细信息
National Software Works (NSW) is a DOD research and development effort designed to provide a software programming environment through the use of computer netting. While there are a number of software technical and managerial considerations, the issues are more complex when the concept of NSW is extended to cover both DOD programmers and government contractors. For example, this approach can provide a ″cradle to grave″ programming environment from the contractual development of a software system through the maintenance of that system by DOD personnel. Issues such as data rights, cost implications, and regulatory matters surround such a use. If the concept is applied to the general economic market place, the issues become even more challenging.
作者：
WILSON, CRAllied Canada
Technical Staff Mississauga Ont Can Allied Canada Technical Staff Mississauga Ont Can
The cooperative processing (coprocessing) of data by inter leaving execution (the heart of large time-sharing systems) on a single computer is considered. The use of Modula-2 with its specific programming constructs p...
详细信息
The cooperative processing (coprocessing) of data by inter leaving execution (the heart of large time-sharing systems) on a single computer is considered. The use of Modula-2 with its specific programming constructs permits the coprocessing to develop a real-time concurrent program and to write operating systems and other low-level software. Two essential mechanisms are shown to implement the mechanics of coprocessing: first, a means of identifying and executing a program that establishes it as a process;second, a method so that two coprocesses can signal each other to coordinate their activities. Modula-2 has facilities for these mechanisms imbedded within it.
A new method for stable merging of two segments A(1..m), A(m+1..n) into A(1..n) in O(n) time is presented. There are no restrictions on n or m and the algorithm requires O(n1/2) workspace. The corresponding procedure ...
详细信息
A new method for stable merging of two segments A(1..m), A(m+1..n) into A(1..n) in O(n) time is presented. There are no restrictions on n or m and the algorithm requires O(n1/2) workspace. The corresponding procedure is given in Pascal together with results of time measurements on samples of random integers.
An analysis is made of a number of aspects of the buffering scheme during the merge phase of an external sort. A discussion is given of the problem of choosing between double buffering, complete single buffering, or s...
详细信息
An analysis is made of a number of aspects of the buffering scheme during the merge phase of an external sort. A discussion is given of the problem of choosing between double buffering, complete single buffering, or something in between, assuming a constraint on the amount of internal memory available for buffering. It is shown that single buffering degrades processing time for a merge pass by an average of from 25% to 37%. It is shown that single buffering is faster than double buffering if and only if there is space available for fewer than 16 buffers.
暂无评论