This paper introduces a new concept regarding information processing in general, but more specifically inter-process communication (IPC) and semantic information processing, where a controlled environment is essential...
详细信息
This paper introduces a new concept regarding information processing in general, but more specifically inter-process communication (IPC) and semantic information processing, where a controlled environment is essential in order to overcome various problems such as deadlocks. The emphasis here is on communication management and the tools necessary for the user to control the IPC environment at both intra- and inter-process levels. The IPC system developed in C is also discussed in detail.
Several variants of quicksort are compared in order to find an efficient internal sorting algorithm for sorting large files in a virtual memory environment. The algorithms compared are original quicksort; ‘Esort’, w...
详细信息
Several variants of quicksort are compared in order to find an efficient internal sorting algorithm for sorting large files in a virtual memory environment. The algorithms compared are original quicksort; ‘Esort’, which uses a fixed memory partition of two page frames; ‘Wsort’, which combines quicksort with merging and sorts one page at a time to reduce page fetches; and ‘Psort’, which uses manual replacement of pages guided by estimates of the interval to the next reference. The comparison is based on several sorting runs on different-size random-ordered files. A memory management simulator with fetch on demand and working set replacement strategy is used to achieve performance measures: the total execution time, the main memory space allocation, and the main memory space-time *** achieves its best performance with a relatively small page size and a very small window size. Reducing page faults by increasing the window size results in excessive space allocation. In an optimal environment, Psort gives some 30-40% smaller space-time integral than quicksort. The space allocation sizes are close to each other, but Psort needs less that half of the page fetches of quicksort. The results for Esort are close to those of quicksort. Wsort does not compete favourably with the original quicksort. In a typical virtual memory environment with a large page size and a large window size, both Esort and Psort perform remarkably better than original quicksort. The space-time integral difference of Psort and quicksort is over 50%, and it increases with an increasing file size.
The article focuses on formalization of the semantics of sequential and parallel sorting algorithms using the apparatus of Glushkov's systems of algorithmic algebras and their modifications. We particularly consid...
详细信息
The article focuses on formalization of the semantics of sequential and parallel sorting algorithms using the apparatus of Glushkov's systems of algorithmic algebras and their modifications. We particularly consider formal transformation of sorting algorithms with the purpose of optimizing them by a set of given criteria.
One common job scheduling objective is to minimize makespan. The problem can be modeled as integer linear programming (ILP) and will often have multiple alternative optimal solutions. However, secondary considerations...
详细信息
One common job scheduling objective is to minimize makespan. The problem can be modeled as integer linear programming (ILP) and will often have multiple alternative optimal solutions. However, secondary considerations, e.g. minimizing the second latest completion time, may very well dictate a preference between solutions with identical makespans. Because of the nature of the primary objective, standard approaches for optimizing a prioritized set of multiple objectives will not work. In this paper we prove that for unit time problems, an appropriate objective function can be formulated, which, when optimized, satisfies both the primary and secondary objectives. Moreover, the new formulation can be modeled as a classical assignment problem (AP). This has the added advantage of efficiency of solution and availability of software. Applications to computer processor scheduling and the military are presented.
Ways of decreasing the number of operations needed to compute the lower bounds of optimal schedules, by reducing the number of time intervals that must be considered, are presented. The bounds apply to a system of ide...
详细信息
Ways of decreasing the number of operations needed to compute the lower bounds of optimal schedules, by reducing the number of time intervals that must be considered, are presented. The bounds apply to a system of identical processors executing a partially ordered set of tasks, with known execution times, using a non-preemptive scheduling strategy. In one approach we find that the required number of intervals depends on the graph. In our other approach, which subsumes the first, the number of intervals is decreased to at most min [D 2 /2, n 2 ], where D is the deadline to complete the tasks and n is the number of tasks. The actual number of intervals for a particular graph can be considerably smaller than this worst case.
This paper presents methodologies capable of quantifying multiprogramming (MP) overhead on a computer system. Two methods which quantify the lower bound on MP overhead, along with a method to determine MP overhead pre...
详细信息
This paper presents methodologies capable of quantifying multiprogramming (MP) overhead on a computer system. Two methods which quantify the lower bound on MP overhead, along with a method to determine MP overhead present in real workloads, are introduced. The techniques are illustrated by determining the percentage of parallel processing time consumed by MP overhead on Alliant multiprocessors. The real workload MP overhead measurements, as well as measurements of other overhead components such as kernel lock spinning, are then used in a comprehensive case study of performance degradation due to overheads. It is found that MP overhead accounts for well over half of the total system overhead. Kernel lock spinning is determined to be a major component of both MP and total system overhead. Correlation analysis is used to uncover underlying relationships between overheads and workload characteristics. It is found that for the workloads studied, MP overhead in the parallel environment is not statistically dependent on the number of parallel jobs being multiprogrammed. However, because of increased kernel contention, serial jobs, even those executing on peripheral processors, are responsible for variation in MP overhead.
The paper presents a new specification style for computations to be executed in an essentially multiprocessor environment. This style is based on two pragmatic premises: (1) the specification is derived from considera...
详细信息
The paper presents a new specification style for computations to be executed in an essentially multiprocessor environment. This style is based on two pragmatic premises: (1) the specification is derived from considerations of system reaction related to system state, rather than to a goal to be achieved, (2) a reaction enabled by a system state is executed independently of any other system activity but its outcome is accepted only if the system “by itself” satisfies a postguard condition, i.e. finds itself in a (possibly different) well-defined state.
To sort an external file on a random access device, the merge sort is the generally accepted method. We present a new algorithm based on Quicksort which allows sorting of external filesin situ. Analytical results and ...
详细信息
To sort an external file on a random access device, the merge sort is the generally accepted method. We present a new algorithm based on Quicksort which allows sorting of external filesin situ. Analytical results and a comparison of test runs indicate that when the new algorithm is applied to a file with suitable key structure, it is competitive to the merge sort in terms of run-time behaviour.
External merge sorting consists of two phases; the formation of initial runs and the merge of the runs into a sorted file (possible in several merge passes). The replacement selection algorithm is typically used to cr...
详细信息
External merge sorting consists of two phases; the formation of initial runs and the merge of the runs into a sorted file (possible in several merge passes). The replacement selection algorithm is typically used to create initial runs. It employs two levels of memory: main memory and a sequential accessed tape-like memory. Natural selection uses a third memory level to increase the average length of an initial run. Although natural selection produces longer runs than replacement selection, it is not competitive because the added overhead is excessive. This paper discusses two other methods of creating longer initial runs in a 3-level memory. Their efficiency is higher than that of natural selection and they also outperform a 3-level replacement selection in most circumstances. The second algorithm has the additional feature that it allows the auxiliary memory to be broken into several smaller parts, thus increasing the average run length. As most computersystems have rotating mass storage, this property is of practical value.
Many new remote procedure calls (RPC) systems are being built to meet different application requirements, and much development effort has been spent on redoing significant parts of the RPC system. This paper describes...
详细信息
Many new remote procedure calls (RPC) systems are being built to meet different application requirements, and much development effort has been spent on redoing significant parts of the RPC system. This paper describes URPC, a toolkit for prototyping new RPC systems. It allows programmers to provide high-level implementations of RPC semantics and to customize supporting RPC services, such as stub generation and name service, to match the requirements of different RPC semantics. This approach increases flexibility in constructing new RPC systems and greatly reduces coding effort. In addition, this approach allows application-specific optimization by increasing the semantic content of individual RPC calls through customization, as well as by allowing programmers to import protocol machine implementations. Thus, the generated prototype RPC implementations can perform as fast as native RPCs.
暂无评论