The article presents the principal features of the POLYP (Problem-Oriented Language for sYstem software programming) system intended for mathematical system software programming and, in particular, for operating syste...
详细信息
The article presents the principal features of the POLYP (Problem-Oriented Language for sYstem software programming) system intended for mathematical system software programming and, in particular, for operating systems. The system has been developed in 1973 in the Federal Republic of Germany by the Scientific Control systems (SCS) Company for IBM/370 and Siemens 4004 computers.
The authors derive optimal lower bounds for this problem with the following area complexity: A = Θ(m(log n - log m + 1)) for k ≥ log n A = Θ(min{2k, m}(|k - log m| + 1)) for k &le log n provided that m &le ...
详细信息
The authors derive optimal lower bounds for this problem with the following area complexity: A = Θ(m(log n - log m + 1)) for k ≥ log n A = Θ(min{2k, m}(|k - log m| + 1)) for k &le log n provided that m &le n. From the result it follows that merging in general is easier than sorting of (m + n)-element arrays. On the otherhand, if m = n and k &le log n then these problems are of the same area complexity. Finally, the paper completes the investigation of area complexity of the problems of ordering.
The Array Management System (AMS) is an integrated set of array management tools designed to increase the productivity of technical programmers engaged in intensive matrix computational applications. These include ana...
详细信息
The Array Management System (AMS) is an integrated set of array management tools designed to increase the productivity of technical programmers engaged in intensive matrix computational applications. These include analog circuit simulator, statistical analysis, dense or sparse equation solving, simulation, and in particular, the finite element program development. AMS is composed of a set of easy-to-use in-core and out-of-core data management subroutines written in FORTRAN 77. The in-core array management subroutines of AMS allow dynamic storage allocation to be accomplished with integer, real, and complex data with a minimum of programming effort. The out-of-core array management subroutines of AMS support simple operations to allow array transfer between in-core and out-of-core systems and allow different programs to access the same data. The out-of-core data management provides for a direct access database file to speed up the input/output operations. Multiple databases are allowed to be accessed by a program; this provides an easy way to share data and restart. This integrated database environment is suitable to be the kernel of a software project with several programmers and data communications among them.
This paper discusses a software control procedure which is often needed in systems that must be highly accurate. Three central processing units (CPU's), with common memory, simultaneously calculate a critical resu...
详细信息
This paper discusses a software control procedure which is often needed in systems that must be highly accurate. Three central processing units (CPU's), with common memory, simultaneously calculate a critical results. The procedure attempts to identify the correct result and any incorrect CPU; the procedure assumes at least two CPU's are correctly working. Three solution methods are considered; the first is instinctively obvious but is paradoxical, the second is complex and the third is surprisingly simple.
To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of mo...
详细信息
To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of an adaptive sorting algorithm Skiena's Melsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra's Smoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we also propose some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well.
This paper is an analysis of program address trace data in a demand-paged computer system with a three-level staging hierarchy. Our primary objective is to explore the data both graphically and numerically, using meth...
详细信息
This paper is an analysis of program address trace data in a demand-paged computer system with a three-level staging hierarchy. Our primary objective is to explore the data both graphically and numerically, using methods that may be useful when other data traces become available. In addition, plausible point-process type models are fit to the data. Such an approach, combining data-analytic procedures with probability modeling, should prove useful in understanding program behavior and thus will aid in the rational design of complex computersystems.
We show how the Hindley/Milner polymorphic type system can be extended to incorporate overloading and subtyping. Our approach is to attach constraints to quantified types in order to restrict the allowed instantiation...
详细信息
We show how the Hindley/Milner polymorphic type system can be extended to incorporate overloading and subtyping. Our approach is to attach constraints to quantified types in order to restrict the allowed instantiations of type variables. We present an algorithm for inferring principal types and prove its soundness and completeness. We find that it is necessary in practice to simplify the inferred types, and we describe techniques for type simplification that involve shape unification, strongly connected components, transitive reduction, and the monotonicities of type formulas.
Partially interpreted program schemas are suggested as a tool for formally specifying and defining the range of applicability of patterns of communication. The body of a schema syntactically resembles a program, but c...
详细信息
Partially interpreted program schemas are suggested as a tool for formally specifying and defining the range of applicability of patterns of communication. The body of a schema syntactically resembles a program, but contains free variables which represent uninterpreted program sections, domains, functions, or other aspects of the program. The specification of the schema includes both applicability requirements and result assertions, as well as specifications for the free variables. A schema may be instantiated to obtain a correct program for a problem statement by matching a problem's assumptions and requirements to a schema specification, and appropriately substituting entities from the problem statement for the free variables in both the specification and the body of the schema. Examples are given of the types of schemas and specifications needed for distributed computing, and of the potential variety of instantiations.
作者：
KUNDE, MUNIV KIEL
INST INFORMAT & PRAKT MATH D-2300 KIEL 1 FED REP GER
Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting N=n1 n 2...n r elements on an n 1×n2×... ×n r array 2(n 1+...+n r?1)+n r data interchange steps are needed asym...
详细信息
Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting N=n1 n 2...n r elements on an n 1×n2×... ×n r array 2(n 1+...+n r?1)+n r data interchange steps are needed asymptotically. For two dimensions these bounds are asymptotically best possible provided that n 1 and n 2 are powers of 2. In this case the generalized s 2-way merge sort of Thompson and Kung turns out to be asymptotically optimal. The minimal asymptotic bound of 2 √2N interchange steps can be obtained only by sorting algorithms suitable for √N/2×√2N meshes. For r≧3 dimensions an analysis of aspect-ratios also demonstrates that there exist mesh-connected architectures which are better suited for sorting than simple r-dimensional cubes.
The paper describes a set of programming facilities for multiprocessor systems, directed toward a transputer architecture with asynchronous connections. The computational model is described, and the basic rules for de...
详细信息
The paper describes a set of programming facilities for multiprocessor systems, directed toward a transputer architecture with asynchronous connections. The computational model is described, and the basic rules for determining objects, data and conditions are introduced. Examples are given to illustrate the development of parallel programs and the processing of dynamic data structures of varying complexity.
暂无评论