The author discusses issues of importance to documenters of open systems in the computer industry. These systems provide a common software environment for users and application programs, and are based on nonproprietar...
详细信息
The author discusses issues of importance to documenters of open systems in the computer industry. These systems provide a common software environment for users and application programs, and are based on nonproprietary technology and industry, national, and international standards. The experience of the Technical Documentation Group at the Open Software Foundation (OSF) is considered as an example. OSF is an international organization that solicits technology through an open process called the request for technology (RFT). OSF supplies to the developers of open systems-based products technologies acquired through the RFT process. The author focuses on such topics as audience definition, documentation set planning, document interchange and tools, internationalization, and writer training and motivation.
It is pointed out that, when looking for new and faster parallel sorting algorithms for use in massively parallel systems it is tempting to investigate promising alternatives from the large body of research done on pa...
详细信息
ISBN:
(纸本)0818620560
It is pointed out that, when looking for new and faster parallel sorting algorithms for use in massively parallel systems it is tempting to investigate promising alternatives from the large body of research done on parallel sorting in the field of theoretical computer science. It is shown how this kind of investigation can be done on a simple but versatile environment for programming and measuring of PRAM (parallel random access machine) algorithms. The practical value of Cole's parallel merge sort algorithm has been investigated by comparing it with Batcher's bitonic sorting. The O(log n) time consumption of Code's algorithm implies that it must be faster than bitonic sorting which is o(log2 n) time, if n is large enough. However, it has been found that bitonic sorting is faster as long as n is less than 1.2 × 1021. Consequently, it is concluded that Cole's logarithmic time algorithm is not fast in practice.
This paper presents a determinstic sorting algorithm, called Sharesort, that sorts n records on an n processor hypercube, shuffle-exchange or cube-connected cycles in O(log n(log log n)2) time in the worst case. The a...
详细信息
ISBN:
(纸本)0897913612
This paper presents a determinstic sorting algorithm, called Sharesort, that sorts n records on an n processor hypercube, shuffle-exchange or cube-connected cycles in O(log n(log log n)2) time in the worst case. The algorithm requires only a constant amount of storage at each processor. The fastest previous deterministic algorithm for this problem was bitonic sort, which runs in O(log2 n) time.
Decision tables are modeled by a harmonium in a manner similar to P. Smolensky's implementation of the two-resistor circuit problem on a harmonium (1984). The lower units consist of the condition combinations, whi...
详细信息
Decision tables are modeled by a harmonium in a manner similar to P. Smolensky's implementation of the two-resistor circuit problem on a harmonium (1984). The lower units consist of the condition combinations, while the knowledge atoms are the actions that are to be carried out in response to the outcome of the conditions. Representational and knowledge vectors are defined. In general, some of the components of these vectors are known and the completion problem consists in filling in the rest of the values that are maximally consistent with the fixed features. The model is described by using harmony theory as the measure of goodness to accomplish the completion task. A comparison with more traditional structures for representing decision tables is made. It is argued that the harmonium is a more flexible and robust model, especially when the environment contains imperfect or incomplete situations.
A method for measuring data locality in four common sorting algorithms is investigated. A modification of the heap data structure exhibiting improved locality is also introduced.
ISBN:
(纸本)0897913485
A method for measuring data locality in four common sorting algorithms is investigated. A modification of the heap data structure exhibiting improved locality is also introduced.
An experimental digital signal processing (DSP) programming environment with a high degree of software integration and user interactivity to support the programming of multiprocessors consisting of different processor...
详细信息
An experimental digital signal processing (DSP) programming environment with a high degree of software integration and user interactivity to support the programming of multiprocessors consisting of different processor types is described. The unifying approach is based on the object-oriented design that is found to be well-suited to most aspects of DSP programming. Another main feature is the seamless integration of different programming levels including assembler, compiler, and a high-level object-based DSP programming system called QuickSig. This is achieved by using Common Lisp as the language of implementation and programming throughout the system. The specific processors used are the TMS320C30 floating-point signal processor for fast DSP, and the M68000 series processors with the 6888x floating-point coprocessor for general-purpose DSP computation.
The problem of sorting a collection of values on a mesh-connected, distributed-memory, SIMD (single-instruction-stream, multiple-data-stream) computer using variants of Batcher's bitonic sort algorithm is consider...
详细信息
ISBN:
(纸本)0818620536
The problem of sorting a collection of values on a mesh-connected, distributed-memory, SIMD (single-instruction-stream, multiple-data-stream) computer using variants of Batcher's bitonic sort algorithm is considered for the case in which the number of values exceeds the number of processors in the machine. In this setting the number of comparisons can be reduced asymptotically if the processors have addressing autonomy (locally indirect addressing), and communication costs can be reduced by judicious domain decomposition. The implementation of several related adaptations of bitonic sort on a MasPar MP-1 is reported. Performance is analyzed in relation to the virtualization ratio VPR. It is concluded that the most reasonable large-array sort for this machine will combine hypercube virtualization with the processor axes transposed dynamically within an xnet embedding.
Replicated execution of distributed programs, which provides a means of masking hardware (processor) failures in a distributed system, is discussed. Application-level entities (processes, objects) are replicated to ex...
详细信息
Replicated execution of distributed programs, which provides a means of masking hardware (processor) failures in a distributed system, is discussed. Application-level entities (processes, objects) are replicated to execute on distinct processors. Such replica entities communicate by message passing. Nondeterminism within the replicas could cause messages to be processed in nonidentical order, producing a divergence of state. Possible sources of nondeterminism are identified, and a generic mechanism for ensuring that nonfaulty replicas process messages in identical order, thereby preventing state divergence among such replicate entities, is presented.
A virtual zero-time VLSI sorting chip is described. The chip has a systolic array architecture and implements the sinking sort algorithm. The basic functional module of the systolic array is detailed, and development ...
详细信息
A virtual zero-time VLSI sorting chip is described. The chip has a systolic array architecture and implements the sinking sort algorithm. The basic functional module of the systolic array is detailed, and development techniques employed as well as functional simulation and results are presented.
Dijkstra's algorithm for finding the length of the longest upsequence within a given sequence of numbers is used as the basis for a case study in the development of a new sorting algorithm. The case study has peda...
详细信息
ISBN:
(纸本)0897913469
Dijkstra's algorithm for finding the length of the longest upsequence within a given sequence of numbers is used as the basis for a case study in the development of a new sorting algorithm. The case study has pedagogic value for several reasons: the motivation for each step in the development of the algorithm is explained;interesting data structures are introduced;the complexity of the algorithm is analyzed using mathematics familiar to first year computer science students;the appendices provide detailed description of the implementation of the algorithm as well as several interesting examples of its use. The proposed algorithm merits attention since it uses O(nlogn) compares in the worst case (actually less than 2nlogn) and O(n) for both ordered or nearly ordered and reverse ordered or nearly reverse ordered sequences.
暂无评论