Some extended semaphore primitives

Summary This paper presents a proposal for synchronizing primitives obtained as an extension of Dijkstra's P, V primitives. The extended primitives are shown to be complete: they can represent any desired interaction between processes without the use of conditionals. The usefulness of these primitives is illustrated by presenting simple solutions to a series of coordination problems of increasing complexity. Two selected problems are used to illustrate disadvantages of existing synchronizing mechanisms. The extended primitives shift some of the burden from the programmer to the system since they are easier to use but more difficult to implement. However, even though each primitive operation may take longer to execute (as compared to the simple P, V primitives) the total system overhead can be substantially less especially for complex coordination problems. The paper presents a straightforward but efficient implementation of the extended primitives.This work was supported in part by the U.S. Atomic Energy Commision under contract AT(11-1 3288) and in part by the Joint Services Electronics Program under contract AFOSR F4620-76-C-0089     

A language and system for the construction and tuning of parallel programs

The programming of efficient parallel software typically requires extensive experimentation with program prototypes. To facilitate such experimentation, any programming system that supports rapid prototyping of parallel programs should provide high-level language primitives with which programs can be explicitly, statically, or dynamically tuned with respect to performance and reliability. Such language primitives should be able to refer conveniently to the information about the executing program and the parallel hardware required for tuning. Such information may include monitoring data about the current or previous program or even hints regarding appropriate tuning decisions. Language primitives and an associated programming system for program tuning are presented. The primitives and system have been implemented, and have been tested with several parallel applications on a network of Unix workstations.<>     

A Scanline Method for Solid Model Display

The modelling of solid objects is becoming increasingly important in the application of computer graphics to a wide variety of problems, such as CAD/CAM, simulation, and molecular modelling. A variety of methods for rendering solid objects exists, including 2-Buffer, Scanline and Ray Tracing. This paper is concerned with a scanline method for the production of still images of complex objects. The implementation of a scanline algorithm is discussed, in conjunction with a consideration of its performance in relation to the z-buffer method.
Many scanline methods cater only for a restricted class of primitives, such as polygons or spheres, whereas this implementation is a general purpose scanline algorithm capable of being extended to handle a variety of primitives. The primitives currently available are polygons, spheres, spheres swept along straight-line trajectories, and cylinders. Polygonal models of cubes, cones and cylinders are also available.
The approach is capable of dealing with "positive" and "negative" volumes, allowing objects with holes to be modelled and displayed. It has further been extended to cater for the inclusion of transparent objects into a scene, and consequently allows the modelling of coloured "glass" objects.     

Extending hoare logic to real-time

Classical Hoare triples are modified to specify and design distributed real-time systems. The assertion language is extended with primitives to express the timing of observable actions. Further the interpretation of triples is adapted such that both terminating and nonterminating computations can be specified. To verify that a concurrent program, with message passing along asynchronous channels, satisfies a real-time specification, we formulate a compositional proof system for our extended Hoare logic. The use of compositionality during top-down design is illustrated by a process control example of a chemical batch processing system.     

Extending hoare logic to real-time

Classical Hoare triples are modified to specify and design distributed real-time systems. The assertion language is extended with primitives to express the timing of observable actions. Further the interpretation of triples is adapted such that both terminating and nonterminating computations can be specified. To verify that a concurrent program, with message passing along asynchronous channels, satisfies a real-time specification, we formulate a compositional proof system for our extended Hoare logic. The use of compositionality during top-down design is illustrated by a process control example of a chemical batch processing system.     

Some unusual primitives in the mira graphical extension of PASCAL

The MIRA system is a very general graphics system which may be useful for almost anyone interested in the production of drawings. The system allows the user to create, save, retrieve, modify and delete any kind of drawing: e.g. free-hand drawings, drawings based on geometrical primitives, algorithmic drawings, data plots, texts. Two-dimensional and three-dimensional drawings can be manipulated. The MIRA system is based on two graphical PASCAL extensions MIRA-2D and MIRA-3D. Two interactive graphical editors GRAFEDIT (two dimensions) and HORIZON (three dimensions) allow the non-specialist user to build complex drawings easily.After an overview of the MIRA system, we present the most unusual primitives, which have been developed for use with this system. These primitives can be divided into different classes: graphical types, figure algebra primitives, figure measure functions, figure recognition predicates, image transformations and animation primitives.     

基于描述逻辑的OntoUML模型的形式化表示

将形式本体理论应用于UML语言的改进是UML的形式化研究的主要方法之一,其中On-toUML是一个概念上完整、语义上清晰和更具本体意义的UML版本。虽然OntoUML基于本体对UML进行了扩充,提供了更为丰富,更能表达现实世界语义的建模原语,但其表达方式不利于在信息系统的设计与开发中应用。本文基于描述逻辑对OntoUML中的关键建模原语及其关系给出了SHIQ形式化表示方法,并进行了实例研究。该方法表达精练、语义清晰,不仅能够表达逻辑清晰的模型,而且保证模型能够正确反映领域事实。这种形式化方法为信息系统概念建模方法提供了理论和应用支撑,在一定程度上推动了OntoUML更为广泛的应用。     

An ACL for a Dynamic System of Agents

In this article we present the design of an ACL for a dynamic system of agents. The ACL includes a set of conversation performatives extended with operations to register, create, and terminate agents. The main design goal at the agent–level is to provide only knowledge–level primitives that are well integrated with the dynamic nature of the system. This goal has been achieved by defining an anonymous interaction protocol which enables agents to request and supply knowledge without considering symbol–level issues concerning management of agent names, routing, and agent reachability. This anonymous interaction protocol exploits a distributed facilitator schema which is hidden at the agent–level and provides mechanisms for registering capabilities of agents and delivering requests according to the competence of agents. We present a formal specification of the ACL and of the underlying architecture, exploiting an algebra of actors, and illustrate it with the help of a graphical notation. This approach provides the basis for discussing dynamic primitives in ACL and for studying properties of dynamic multi agent systems, for example concerning the behavior of agents and the correctness of their conversation policies.     

Dispatcher primitives for the construction of operating system kernels

Summary The main subject of this paper is the definition of a general set of dispatcher primitives which have been proved to be a suitable basis for the structured design of operating system kernels. The use of the primitives in the construction of kernel programs is demonstrated.     

Perceptual primitives from an extended 4D Hough transform

Directional features extracted from Gabor wavelets responses were used to train a structure of self-organising maps, thus classifying each pixel in the image within a neuron-map. Resulting directional primitives were grouped into perceptual primitives introducing an extended 4D Hough transform to group pixels with similar directional features. These can then be used as perceptual primitives to detect salient structures. The proposed method has independently fixed parameters that do not need to be tuned for different kind or quality of images. We present results in application to noisy FLIR images and show that line primitives for complex structures, such as bridges, or simple structures, such as runways, can be found by this approach. We compare and demonstrate the quality of our results with those obtained through a parameter-dependent traditional Canny edge detector and Hough line finding process.     

基于卫星网络管理的SNMP扩展原语设计

针对卫星网中卫星节点的动态性和管理域动态划分的特点,提出卫星网络动态管理域划分的注册注销机制。地面分管理站向视域内的卫星发送注册广播分组,星上SNMP代理收到广播分组后采用链路延迟测试应答。根据该机制扩展了SNMP的原语,对原语的定义遵循RFC1157规范,可采用BER编码。该设计实现了SNMP协议对基于注册注销机制的动态管理域划分策略的支持。     

From on-line sketching to 2D and 3D geometry: a system based on fuzzy knowledge

The paper describes the development of a fuzzy knowledge-based prototype system for conceptual design. This real time system is designed to infer user's sketching intentions, to segment sketched input and generate corresponding geometric primitives: straight lines, circles; arcs, ellipses, elliptical arcs, and B-spline curves. Topology information (connectivity, unitary constraints and pairwise constraints) is received dynamically from 2D sketched input and primitives. From the 2D topology information, a more accurate 2D geometry can be built up by applying a 2D geometric constraint solver. Subsequently, 3D geometry can be received feature by feature incrementally. Each feature can be recognised by inference knowledge in terms of matching its 2D primitive configurations and connection relationships. The system accepts not only sketched input, working as an automatic design tool, but also accepts user interactive input of both 2D primitives and special positional 3D primitives. This makes it easy and friendly to use. The system has been tested with a number of sketched inputs of 2D and 3D geometry.     

The Argonne/GMD macros in FORTRAN for portable parallel programming and their implementation on the Intel iPSC/2

A macro package for expressing message passing functions within parallel FORTRAN program is presented. It makes the user program fully portable among all parallel computers where the macros are implemented. The implementation on the Intel iPSC/2 hypercube is discussed in more detail. New message passing primitives have been added to the iPSC/2 operating system, offering the user a broader functionality at no efficiency loss. The full macro set, using these primitives, works with the same performance as the original Intel primitives.     

Process scheduling and UNIX semaphores

Semaphores have been used extensively in programming concurrent tasks. Various extensions have been proposed for problems in which traditional semaphores turned out to be difficult to use. The extended semaphore primitives investigated here are based on the version of semaphores implemented in UNIX System V. Implementation issues are discussed and practical illustrations of their use are provided. In particular, algorithms for a variety of common process scheduling schemes are shown. These solutions are evaluated and the strengths and weaknesses of UNIX semaphores are discussed.     

Synchronization and control of parallel algorithms

We propose a modest collection of primitives for synchronization and control in parallel numerical algorithms. These are phrased in a syntax that is compatible with FORTRAN, creating a publication language for parallel software. A preprocessor may be used to map code written in this extended FORTRAN into standard FORTRAN with calls to the run-time libraries of the various parallel systems now in use. We solicit the reader's comments on the clarity, as well as the adequacy, of the primitives we have proposed.     

Strategies for integrating knowledge-based systems techniques within conventional software environments

This article discusses strategies for integrating knowledge-based systems techniques with conventional computer science techniques. The effect of such an approach has led to the production of an intelligent systems development environment called INDEX. INDEX supports a layered architecture to enable expert system functionality to be generated and integrated at language level, tool level, and system level within a traditional software environment. At the language level, INDEX provides a set of expert system primitives describing low-level operations of an expert system. These primitives can be accessed from most of the conventional languages. At tool level, expert system primitives and relevant INDEX facilities are used in producing expert system tools and various mediation tools for tool integration. At the system level, INDEX can be used to build integrated/coordinated systems. Several applications have been given to demonstrate the effectiveness of our approach, and its future directions. © 1996 John Wiley & Sons, Inc.     

Unifying and optimizing parallel linear algebra algorithms

Two issues in linear algebra algorithms for multicomputers are addressed. First, how to unify parallel implementations of the same algorithm in a decomposition-independent way. Second, how to optimize naive parallel programs maintaining the decomposition independence. Several matrix decompositions are viewed as instances of a more general allocation function called subcube matrix decomposition. By this meta-decomposition, a programming environment characterized by general primitives that allow one to design meta-algorithms independently of a particular decomposition. The authors apply such a framework to the parallel solution of dense matrices. This demonstrates that most of the existing algorithms can be derived by suitably setting the primitives used in the meta-algorithm. A further application of this programming style concerns the optimization of parallel algorithms. The idea to overlap communication and computation has been extended from 1-D decompositions to 2-D decompositions. Thus, a first attempt towards a decomposition-independent definition of such optimization strategies is provided