The specification language Z (“zed”), based on set theory, has been used to define a microprocessor based system in a formal notation. The 8-bit Motorola 6800 was chosen as an example because of its simplicity. Memo...
详细信息
The specification language Z (“zed”), based on set theory, has been used to define a microprocessor based system in a formal notation. The 8-bit Motorola 6800 was chosen as an example because of its simplicity. Memory configuration and interrupts were included. This paper presents parts of this specification. The use of a formal description language allows the possibility of verification of the instruction set. Z could also be used at the design stage. Additionally, the use of Z combined with informal text is sufficently readable for the specification to be used for documentation purposes. With the experience gained, a more complicated or a completely new microprocessor could now be attempted.
We present an optimal algorithm for sorting n integers in the range [1, n(c)] (for any constant c) for the EREW PRAM model where the word length is n(epsilon), for any epsilon > 0. Using this algorithm, the best kn...
详细信息
We present an optimal algorithm for sorting n integers in the range [1, n(c)] (for any constant c) for the EREW PRAM model where the word length is n(epsilon), for any epsilon > 0. Using this algorithm, the best known upper bound for integer sorting on the (O(log n) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorithm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.
Event-based middleware is currently being applied for application component integration in a range of application domains. As a result, a variety of event services has been proposed to address different requirements. ...
详细信息
Event-based middleware is currently being applied for application component integration in a range of application domains. As a result, a variety of event services has been proposed to address different requirements. In order to aid the understanding of the relationships between these systems, this paper presents a taxonomy of distributed event-based programmingsystems. The taxonomy is structured as a hierarchy of the properties of a distributed event system and may be used as a framework to describe such a system according to its properties. The taxonomy identifies a set of fundamental properties of event systems and categorizes them according to the event model supported and the structure of the event service. Event services are further classified according to their organization and their interaction models, as well as other functional and non-functional features.
We consider the problem of merging m disjoint ordered lists, each of size n/m. We determine up to a constant factor the worst case and average case deterministic and randomized parallel comparison complexity of the pr...
详细信息
We consider the problem of merging m disjoint ordered lists, each of size n/m. We determine up to a constant factor the worst case and average case deterministic and randomized parallel comparison complexity of the problem for all the range of n, m and p where p is the number of processors used. The worst case deterministic time complexity is [GRAPHICS] That means [GRAPHICS] and [GRAPHICS] Clearly merging two equal lists and sorting are special cases of this problem for m = 2 and m = n respectively. We also prove that these bounds hold for randomized algorithms and even for the average case of deterministic or randomized ones. Therefore the average case of the best deterministic or randomized algorithm for this problem is not faster than the worst case of the best deterministic one by more than a constant factor.
User interface modelling (UIM) is basically a method for gathering user requirements that are applicable when designing the user interface to an information system. UIM is to be used as a complement to use case modell...
详细信息
User interface modelling (UIM) is basically a method for gathering user requirements that are applicable when designing the user interface to an information system. UIM is to be used as a complement to use case modelling (Jacobson, Christerson, Jonsson & Overgaard, 1992) in the system development process. An actor model, a goal model and a work model are specified during sessions where the end-users cooperate with software engineers and user-interface designers. The actor model is a description of characteristics for each category of users. The goal model is a list of high-level goals the users want to achieve. The work model is a specification of work situations, information objects and actions, and properties of attributes and operations, suitable for the design. UIM does not describe a step-by-step procedure on how to create usable interfaces. Interface design is partially a creative process than cannot be completely described with a method. However, the design process can be facilitated if the design decisions are based on a substantial model defining the users' requirements for the user interface. This model is created during UIM sessions. The method has been tested in different development projects at the Swedish National Tax Board. It has been shown to provide useful input to the user-interface design process. (C) 1999 Academic Press.
In this paper we develop a new parallel algorithm for sorting which has a time complexity of O(log n) and requires n2/log n processors. The algorithm can be readily mapped on an SIMD mesh connected array of processors...
详细信息
In this paper we develop a new parallel algorithm for sorting which has a time complexity of O(log n) and requires n2/log n processors. The algorithm can be readily mapped on an SIMD mesh connected array of processors which has all the featuresof efficient VLSI implementation. The corresponding hardware algorithm maintains the O(Log n) execution time and has a lowO(n) interprocessor communication *** November 1987. revised February 1990.
Efficient scheduling techniques of computing resources are essential for achieving satisfactory performance for users as computersystems and their applications become more complex. In this paper, we survey research o...
详细信息
Efficient scheduling techniques of computing resources are essential for achieving satisfactory performance for users as computersystems and their applications become more complex. In this paper, we survey research on scheduling algorithms, review previous classifications of scheduling problems, and present a broader classification scheme. Using a uniform terminology for scheduling strategies and the new classification scheme, previous work on scheduling strategies is reviewed and trends in scheduling research are identified. Finally, a methodology for developing scheduling strategies is presented.
A method of evaluating recursively defined functions which uses two (or more) stacks is described in this paper. This method is designed to reduce the stack storage needed and requires simpler ‘linkage’ information ...
详细信息
A method of evaluating recursively defined functions which uses two (or more) stacks is described in this paper. This method is designed to reduce the stack storage needed and requires simpler ‘linkage’ information than the single stack method. In addition, a study of ‘go-to’ (or iterative) type recursive definitions is made and it is shown that these require bounded stack storage for their evaluation.
We present a simple algorithm for emulating an N -processor CROW PRAM on an N -ode butterfly. Each step of the PRAM is emulated in time O (log N ) with high probability, using FIFO queues of size O (1) at each node. T...
详细信息
We present a simple algorithm for emulating an N -processor CROW PRAM on an N -ode butterfly. Each step of the PRAM is emulated in time O (log N ) with high probability, using FIFO queues of size O (1) at each node. The only use of randomization is in selecting a hash function to distribute the shared address space of the PRAM onto the nodes of the butterfly. The routing itself is both deterministic and oblivious, and messages are combined without the use of associative memories or explicit sorting. As a corollary we improve the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock. Besides being optimal, our algorithm has the advantage of extreme simplicity and is readily suited for use in practice.
Code generation techniques are used to program an application characterized by complexity arising from many special cases, and rapid changes due to advances in the state of the art. A formal notation—an inverted deci...
详细信息
Code generation techniques are used to program an application characterized by complexity arising from many special cases, and rapid changes due to advances in the state of the art. A formal notation—an inverted decision table written in a propositional logic form—is developed as a means for allowing expert users to describe the application in a knowledge base that code generators then can use to create production code. The complete system described in the paper automatically transforms a one thousand-page specification into a running program. The development of this system is an example of the formalization of the specification of a complex application. In this case the application is a part of the Job Management Operations System, an operational support system to aid regional Bell Operating Company construction and engineering processes. The techniques described, however, can be generalized.
暂无评论