15862425
A Fixpoint Theory for Non-monotonic Parallelism
This paper studies parallel recursions. The trace specification language used in this paper incorporates sequentiality, nondeterminism, reactiveness (including infinite traces), conjunctive parallelism and general recursion. The language is the minimum of its kind and thus provides a context in which we can study parallel recursions in general. In order to use Tarski's theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. A theorem of this paper shows that no appropriate order exists. Tarski's theorem alone is not enough to determine the fixpoints of parallel recursions. Instead of using Tarski's theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. Such reasoning is supported by the laws of a new composition called partition. We propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. The surprising result is that although a recursion may not be monotonic with regard to the lexical order, it must have the partitioned fixpoint, which equals the least lexical-order fixpoint. Since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. Major existing fixpoint techniques simply become special cases of the partitioned fixpoint. For example, an Egli-Milner-monotonic recursion has its least Egli-Milner fixpoint, which can be shown to be the same as the partitioned fixpoint. The new technique is more general than the least Egli-Milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not Egli-Milner monotonic. Examples of non-monotonic recursions with fair-interleaving parallelism are studied. Their partitioned fixpoints are shown to be consistent with our intuitions.
17662809
Hierarchical Organisation of Predicate-Semantic Models
This paper introduces techniques to organise predicate- semantic models in a hierarchical structure so that a new model can inherit the laws of the existing ones. Generic composition is used to simplify the manipulation of predicates. Necessary restrictions are imposed on the definition of each model so that the inheritance relation can be established by checking a few conditions on the healthiness conditions and the commands. Much of the checking can be supported by laws of generic composition. The techniques also help simplify the proof of well-definedness of program combinators (i.e. their closure in the semantic space) so that we no longer need to prove it (in predicate calculus) for every new model.
10370670
Top-Down Design of Bulk-Synchronous Parallel Programs
This paper studies top-down program development techniques for Bulk-Synchronous Parallelism. In that context a specification formalism LOGS, for 'the Logic of Global Synchrony', has been proposed for the specification and high-level development of BSP designs. This paper extends the use of LOGS to provide support for the protection of local variables in BSP programs, thus completing the link between specifications and programs.
8121039
Logic of global synchrony
An intermediate-level specification formalism (i.e., specification language supported by laws and a semantic model), Logs, is presented for PRAM and BSP styles of parallel programming. It extends pre-post sequential semantics to reveal states at points of global synchronization. The result is an integration of the pre-post and reactive-process styles of specification. The language consists of only six commands from which other useful commands can be derived. Parallel composition is simply logical conjunction and hence compositional. A simple predicative semantics and a complete set of algebraic laws are presented. Novel ingredients include the separation, in our reactive context, of the processes for nontermination and for abortion which coincide in standard programming models; the use of partitions, combining the terminating behavior of one program with the nonterminating behavior of another; and a fixpoint operator, the partitioned fixpoint. Our semantics benefits from the recent "healthiness function" approach for predicative semantics. Use of Logs, along with the laws for reasoning about it, is demonstrated on two problems: matrix multiplication (a terminating numerical computation) and the dining philosophers (a reactive computation). The style of reasoning is so close to programming practice that direct transformation from Logs specifications to real PRAM and BSP programs becomes possible.
3166137
Integrating Temporal Logics
In this paper, we study the predicative semantics of different temporal logics and the relationships between them. We use a notation called generic composition to simplify the manipulation of predicates. The modalities of possibility and necessity become generic composition and its inverse of converse respectively. The relationships between different temporal logics are also characterised as such modalities. Formal reasoning is carried out at the level of predicative semantics and supported by the higher-level laws of generic composition and its inverse. Various temporal domains are unified under a notion called resource cumulation. Temporal logics based on these temporal domains can be readily defined, and their axioms identified. The formalism provides a framework in which human experience about system development can be formalised as refinement laws. The approach is demonstrated in the transformation from Duration Calculus to Temporal Logic of Actions. A number of common design patterns are studied. The refinement laws identified are then applied to the case study of water pump controlling.
10148394
Generating C Code from LOGS Specifications
This paper introduces a tool that automatically translates a concrete form of specifications into C code linked with BSPlib. The translation tool is rigorously developed with important safety properties proved. A Logs specification for Bulk-Synchronous Parallelism is a relation of an initial state, a final state and some intermediate states. Nondeterminism and parallelism correspond to disjunction and conjunction respectively. Various advanced specification commands can be derived from the basic ones. The translator checks syntax, freedom of communication interference, type consistency and communication dependencies before generating the target code. Static analysis (including both static checkings and translation) is presented in abstract interpretation. It is shown that a few laws are complete for transforming any specification into a normal form. These laws are satisfied by the abstract functions. We demonstrate the actual effects of the abstract functions by applying them on the normal form. The approach has been implemented using an object-oriented language.
12775848
Analyzing Inconsistency Toward Enhancing Integration of Biological Molecular Databases
The rapid growth of biological databases not only provides biologists with abundant data but also presents a big challenge in relation to the analysis of data. Many data analysis approaches such as data mining, information retrieval and machine learning have been used to extract frequent patterns from diverse biological databases. However, the discrepancies, due to the differences in the structure of databases and their terminologies, result in a significant lack of interoperability. Although ontology-based approaches have been used to integrate biological databases, the inconsistent analysis of biological databases has been greatly disregarded. This paper presents a method by which to measure the degree of inconsistency between biological databases. It not only presents a guideline for correct and efficient database integration, but also exposes high quality data for data mining and knowledge discovery.
1752675
Storing and Discovering Critical Workflows from Log in Scientific Exploration
This paper aims at effectively reproducing the results of previous scientific workflow executions. We first identify the information that needs to be recorded in a workflow execution log, based on which we then determine the data flow among experiments. To effectively record a workflow execution log in a relational database management system (RDBMS) when the workflow design is absent, we propose a generic relational storage schema. Then techniques have been designed to automatically discover the minimal set of experiments that must be performed in order to reproduce a scientific result by posing appropriate SQL queries. Although such SQL queries can be evaluated using an off-the-shelf database system, we investigate the unique characteristics of the workflow log data and optimization techniques for evaluating such SQL queries efficiently.
33634754
Reconstruction and Fusion of Multi-modality Spinal Images
14057550
Exploration on the commonality of hierarchical clustering algorithms
Many clustering algorithms have been devised. The published account of each algorithm emphasizes how it is different from previous algorithms. However, similarities among agglomerative hierarchical algorithms are greater than commonly supposed. For example, several algorithms perform merging by the single link (SLINK, OPTICS) and some algorithms perform merging by the edge cut criterion (CHAMELEON, ROCK). Some algorithms use the square of the original adjacency matrix (OPTICS, ROCK). Our goals are to compose a not very long list of methods used by the various algorithms; to locate each algorithm in this space of methods; and to devise new algorithms that improve upon the previous methods.
8136301
Architecture classification for SOA-based applications
The architecture of SOA-based applications is different from traditional software architecture where the architecture is mainly static. The architecture of an SOA-based application is dynamic, i.e., the application may be composed at runtime using existing services. Thus SOA has provided a new direction for software architecture study, where the architecture is determined at runtime and architecture can be dynamically changed at runtime to meet the new software requirements. This paper proposes an architecture classification scheme for SOA-based applications. Using this classification, several well-known SOA-based applications are reviewed including the architectures proposed and adopted by major computer companies and standard organizations. The architecture classification provides a unified way to evaluate a variety of architectures for SOA-based applications