36039309
Consistency in Dataflow Graphs
Analytical properties of programming languages with dataflow graph semantics are discussed. It is shown that one of the most serious problems with these languages is that subtle inconsistencies between parts of the dataflow graph can be inadvertently created. These inconsistencies can lead to deadlock, or in the case of nonterminating programs, to unbounded memory requirements. Consistency is defined to mean that the same number of tokens is consumed as produced on any arc, in the long run. A token-flow model is developed for testing for inconsistency. The method is a generalization of consistency checks for synchronous dataflow (SDF) graphs. The token-flow model is compared to similar tests applied to hybrid dynamical systems. It is argued that dataflow semantics make steady-state analysis possible, leading to a simpler method in most cases. >
61727598
Comparing models of computation
We give a denotational framework (a meta model) within which certain properties of models of computation can be understood and compared. It describes concurrent processes as sets of possible behaviors. Compositions of processes are given as intersections of their behaviors. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. Synchronous systems contain synchronous signals. Strict causality (in timed systems) and continuity (in untimed systems) ensure determinacy under certain technical conditions. The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, Petri nets, and discrete-event systems.
5648139
The problem with threads
For concurrent programming to become mainstream, we must discard threads as a programming model. Nondeterminism should be judiciously and carefully introduced where needed, and it should be explicit in programs. In general-purpose software engineering practice, we have reached a point where one approach to concurrent programming dominates all others namely, threads, sequential processes that share memory. They represent a key concurrency model supported by modern computers, programming languages, and operating systems. In scientific computing, where performance requirements have long demanded concurrent programming, data-parallel language extensions and message-passing libraries such as PVM, MPI, and OpenMP dominate over threads for concurrent programming. Computer architectures intended for scientific computing often differ significantly from so-called general-purpose architectures.
10518317
Embedded Software
Syntax It is useful to separate syntactic issues from semantic issues. An abstract syntax defines how a design can be decomposed into interconnected components, without being concerned with how a design is represented on paper or in a computer file (that is the concern of the concrete syntax). An abstract syntax is also not concerned with the meaning of the interconnections of components, nor even what a component is. A design is a set of components and relationships among them, where the relationships conform to this abstract syntax. Here, we describe the abstract syntax using informal diagrams that illustrate these sets and relations by giving use cases, although formalizing the abstract syntax is necessary for precision. Port Port Actor Actor
10851913
Taming heterogeneity - the Ptolemy approach
Modern embedded computing systems tend to be heterogeneous in the sense of being composed of subsystems with very different characteristics, which communicate and interact in a variety of ways-synchronous or asynchronous, buffered or unbuffered, etc. Obviously, when designing such systems, a modeling language needs to reflect this heterogeneity. Today's modeling environments usually offer a variant of what we call amorphous heterogeneity to address this problem. This paper argues that modeling systems in this manner leads to unexpected and hard-to-analyze interactions between the communication mechanisms and proposes a more structured approach to heterogeneity, called hierarchical heterogeneity, to solve this problem. It proposes a model structure and semantic framework that support this form of heterogeneity, and discusses the issues arising from heterogeneous component interaction and the desire for component reuse. It introduces the notion of domain polymorphism as a way to address these issues.
1955659
A framework for comparing models of computation
We give a denotational framework (a "meta model") within which certain properties of models of computation can be compared. It describes concurrent processes in general terms as sets of possible behaviors. A process is determinate if, given the constraints imposed by the inputs, there are exactly one or exactly zero behaviors. Compositions of processes are processes with behaviors in the intersection of the behaviors of the component processes. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. Synchronous processes have only synchronous signals as behaviors. Strict causality (in timed tag systems) and continuity (in untimed tag systems) ensure determinacy under certain technical conditions. The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, Petri nets, and discrete-event systems.
36370882
Multi-agent Based Hybrid System for Dynamic Web-Content Adaptation
Context-aware adaptation service is rapidly becoming an important issue. This service overcomes the limitations of wireless devices and maintains adequate service levels in changing environments. The majority of existing studies concentrate on adaptation modules on the client, proxy, or server. These existing studies thus suffer from the problem of having the workload concentrated on a single system. This means that increasing the number of users increases the response time of a user’s request. In this paper, the adaptation module is dispersed and arranged over the client, proxy, and server. The module monitors the context of each system and creates a dispersed adaptation system, optimized for efficient operation. Through this method, faster adaptation work is made possible, even when the number of users increases, and the dividing workload makes more stable system operation possible. In order to evaluate the proposed system, a prototype is constructed and dispersed operations are tested using multimedia content, simulating server overload and comparing the response times and system stability with existing server based adaptation systems. The effectiveness of the system is confirmed through the results.
14010108
conga: A Framework for Adaptive Conducting Gesture Analysis
Designing a conducting gesture analysis system for public spaces poses unique challenges. We present conga, a software framework that enables automatic recognition and interpretation of conducting gestures. conga is able to recognize multiple types of gestures with varying levels of difficulty for the user to perform, from a standard four-beat pattern, to simplified up-down conducting movements, to no pattern at all. conga provides an extendable library of feature detectors linked together into a directed acyclic graph; these graphs represent the various conducting patterns as gesture profiles. At run-time, conga searches for the best profile to match a user's gestures in real-time, and uses a beat prediction algorithm to provide results at the sub-beat level, in addition to output values such as tempo, gesture size, and the gesture's geometric center. Unlike some previous approaches, conga does not need to be trained with sample data before use. Our preliminary user tests show that conga has a beat recognition rate of over 90%. conga is deployed as the gesture recognition system for Maestro!, an interactive conducting exhibit that opened in the Betty Brinn Children's Museum in Milwaukee, USA in March 2006.
7453458
Designing time-based interactions with multimedia
The current model of time in multimedia frameworks poses particular problems when designing multimedia systems with time-based interaction. We propose to expand and extend an existing distinction between semantic time and real time from music and film theory to multimedia systems design. The semantic time concept also forms the foundation of a new software framework for multimedia systems that we are building, that, unlike most existing frameworks, includes mechanisms for time-based effects such as time-stretching.
24643318
Context Adaptive Self-configuration System Based on Multi-agent
This paper proposes an adaptive resource self-management system that collects system resources, user information, and usage patterns as context information for utilization in self-configuration. This system will ease the system maintenance burden on users by automating a large portion of the configuration tasks such as; install, reconfiguration and update, while also decreasing cost and errors. Working from the gathered context information, this system allows users to select and install appropriate components for their system context. This also offers a more personalized configuration setting by using user's existing application setting and usage pattern. To avoid a center server overload when transferring and managing related files, we employ Peerto- Peer method. A prototype was developed to evaluate the system with a comparison study using the conventional methods of manual configuration and MS-IBM systems was conducted to validate the proposed system in terms of functional capacity, install time, etc...
17704367
A Parallel, Linear Programming-based Heuristic for Large-Scale Set Partitioning Problems
We describe a parallel, linear programming and implication-based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primaldual subproblem simplex method is used for solving the linear programming relaxation, which breaks the linear programming solution process into natural phases from which we can exploit information to find good solutions on the various processors. Implications from the probing operation are shared among the processors. Combining these techniques allows us to obtain solutions to large and difficult problems in a reasonable amount of computing time.