A graphical development and debugging environment for parallel programs

To provide high-level graphical support for PVM (Parallel Virtual Machine) based program development, a complex programming environment (GRADE) is being developed. GRADE currently provides tools to construct, execute, debug, monitor and visualize message-passing parallel programs. It offers a high-level graphical programming abstraction mechanism to construct parallel applications by introducing a new graphical language called GRAPNEL. GRADE also provides the programmer with the same graphical user interface during the program design and debugging stages. A distributed debugging engine (DDBG) assists the user in debugging GRAPNEL programs on distributed memory computer architectures. Tape/PVM and PROVE support the performance monitoring and visualization of parallel programs developed in the GRADE environment.     

An assessment of concurrent Pascal

This paper assesses Concurrent Pascal against its design aims. The language is shown to be suitable for writing reliable non-trivial concurrent applications programs and operating systems. The major weakness of the language is its inability to provide an environment for other Concurrent Pascal programs. A new language construct, group, is proposed to remedy this difficulty.     

Analysis and testing of programs with exception handling constructs

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of software engineering tasks, including structural and regression testing, dynamic execution profiling, static and dynamic slicing, and program understanding. To be applicable to programs in languages such as Java and C++, these analysis techniques must account for the effects of exception occurrences and exception handling constructs; failure to do so can cause the analysis techniques to compute incorrect results and, thus, limit the usefulness of the applications that use them. This paper discusses the effects of exception handling constructs on several analysis techniques. The paper presents techniques to construct representations for programs with explicit exception occurrences-exceptions that are raised explicitly through throw statements-and exception handling constructs. The paper presents algorithms that use these representations to perform the desired analyses. The paper also discusses several software engineering applications that use these analyses. Finally, the paper describes empirical results pertaining to the occurrence of exception handling constructs in Java programs and their effect on some analysis tasks     

An execution profiler for window-oriented applications

Execution profiles are important in analyzing the performance of computer programs on a given computer system. However, accurate and complete profiles are difficult to arrive at for programs that follow the client-server model of computing, as in the popular X Window System. In X Window applications, considerable computation is invoked at the display server and this computation is an important part of the overall execution profile. The profiler presented in this paper generates meaningful profiles for X Window applications by estimating the time spent in servicing the messages in the display server. The central idea is to analyze a protocol-level trace of the interaction between the application and the display server and thereby construct an execution profile from the trace and a set of metrics about the target display server. Experience using the profiler for examining bottlenecks is presented.     

Review of generic software for environmental engineering applications

Generic software such as spreadsheet and data base programs provide utilities that can be used to construct routines for various applications. The specific used is determined by the user. Generic software allows interactive programming and data manipulation. These programs have dramatically changed the everyday use of microcomputers by creating an easy and flexible interace ofr inexperienced computer users to create their own user defined routines without requiring any formal programming skills. Data entry and retrieval are extremely easy, as well as transfer of data between different software packages. This paper review some of the commonly used generic software packages, focusing on spreadsheets, data base programs, and integrated software packages for IBM PC compatible microcomputers.Several commercial programs, varying in price and capability, are evaluated to determine their applicability in environmental engineering calculations Evaluations were made in terms of the potential use in engineering calculations and other applications, the mathematical capacity, speed of calculations, versatility, and user friendliness. Data transfer between different programare extremely crucial for engineering applications. It is achieved by using “standard” file formats, such as SIF and DIF files.     

Telescoping Languages: A Strategy for Automatic Generation of Scientific Problem-Solving Systems from Annotated Libraries

As machines and programs have become more complex, the process of programming applications that can exploit the power of high-performance systems has become more difficult and correspondingly more labor-intensive. This has substantially widened the software gap—the discrepancy between the need for new software and the aggregate capacity of the workforce to produce it. This problem has been compounded by the slow growth of programming productivity, especially for high-performance programs, over the past two decades. One way to bridge this gap is to make it possible for end users to develop programs in high-level domain-specific programming systems. In the past, a major impediment to the acceptance of such systems has been the poor performance of the resulting applications. To address this problem, we are developing a new compiler-based infrastructure, called TeleGen, that will make it practical to construct efficient domain-specific high-level languages from annotated component libraries. We call these languages telescoping languages, because they can be nested within one another. For programs written in telescoping languages, high performance and reasonable compilation times can be achieved by exhaustively analyzing the component libraries in advance to produce a language processor that recognizes and optimizes library operations as primitives in the language. The key to making this strategy practical is to keep compile times low by generating a custom compiler with extensive built-in knowledge of the underlying libraries. The goal is to achieve compile times that are linearly proportional to the size of the program presented by the user, rather than to the aggregate size of that program plus the base libraries.     

面向协同应用的通用协作语言研究

研究和探讨一种能够灵活定制不同协同应用方案的编程语言。对CSCW协同应用中的协作机制和交互特征进行分析，抽象出协同应用中最具共性的基本协作元素，对这些基本元素进行定义和描述。提出将协作问题从计算应用问题中分离出来的方案。对于一个给定的应用，可以构造多种协作方案。使最终用户可选择最符合自己需要的协作方案和交互规则来进行他们之间协同工作，并且还可在协同工作会话过程中改变协作交互规则。     

Deductive Synthesis of Numerical Simulation Programs from Networks of Algebraic and Ordinary Differential Equations

Scientists and engineers face recurring problems of constructing, testing and modifying numerical simulation programs. The process of coding and revising such simulators is extremely time-consuming, because they are almost always written in conventional programming languages. Scientists and engineers can therefore benefit from software that facilitates construction of programs for simulating physical systems. Our research adapts the methodology of deductive program synthesis to the problem of constructing numerical simulation codes. We have focused on simulators that can be represented as second order functional programs composed of numerical integration and root extraction routines. We have developed a system that uses first order Horn logic to synthesize numerical simulators built from these components. Our approach is based on two ideas: first, we axiomatize only the relationship between integration and differentiation. We neither attempt nor require a complete axiomatization of mathematical analysis. Second, our system uses a representation in which functions are reified as objects. Function objects are encoded as lambda expressions. Our knowledge base includes an axiomatization of term equality in the lambda calculus. It also includes axioms defining the semantics of numerical integration and root extraction routines. We use depth bounded SLD resolution to construct proofs and synthesize programs. Our system has successfully constructed numerical simulators for computational design of jet engine nozzles and sailing yachts, among others. Our results demonstrate that deductive synthesis techniques can be used to construct numerical simulation programs for realistic applications.     

Minimal cost replication of dynamic Web contents under flat update delivery

Dynamic Web contents are generated by running application programs on base data which often change frequently. Geographically replicating the applications that construct these contents (including the programs and the related data they access) is an effective approach to improve their access latency. To maintain the freshness of an object replica, the new version of the object either has to be fetched from remote servers or be reconstructed locally when the origin copy is updated. We present a theoretical study on geographical replication of dynamic Web contents with the objective of minimizing the consistency management costs in terms of update transfers and object reconstruction. The dependencies among dynamic objects and base data are modeled as a directed acyclic graph. We formulate the minimum cost replication problem under a flat framework of update delivery. The problem is solved by first transforming it into a minimum cut problem in a flow network. A polynomial-time algorithm is then proposed to compute the optimal replication strategy which designates where each object should be replicated and how to keep the replicas up-to-date.     

Automatic equivalence checking of programs with uninterpreted functions and integer arithmetic

Proving equivalence of programs has several important applications, including algorithm recognition, regression checking, compiler optimization verification and validation, and information flow checking. Despite being a topic with so many important applications, program equivalence checking has seen little advances over the past decades due to its inherent (high) complexity. In this paper, we propose, to the best of our knowledge, the first semi-algorithm for the automatic verification of partial equivalence of two programs over the combined theory of uninterpreted function symbols and integer arithmetic (UF+IA). The proposed algorithm supports, in particular, programs with nested loops. The crux of the technique is a transformation of uninterpreted functions (UFs) applications into integer polynomials, which enables the precise summarization of loops with UF applications using recurrences. The equivalence checking algorithm then proceeds on loop-free, integer only programs. We implemented the proposed technique in CORK, a tool that automatically verifies the correctness of compiler optimizations, and we show that it can prove more optimizations correct than state-of-the-art techniques.     

领域知识图谱快速构建和应用框架

快速构建和应用领域知识图谱(domain knowledge graphs, DKG)已成为企业的迫切需求。然而,领域知识图谱的快速构建和应用仍然存在问题:1）构建前,复杂领域场景涉及知识维度广,业务专家短时间内难以构建完备的领域schema;2）构建中,业务和技术专家深度耦合,图谱构建缓慢,难以适应业务快速发展需求;3）构建后,图谱应用严重依赖技术人员开发,业务专家无法自主基于领域知识图谱探索问题解决方案。为解决上述问题,本文提出了领域知识图谱的快速构建和应用框架,其中包括:多人协作构建领域schema解决领域知识的复杂性问题,将业务和技术专家解耦合,提高领域知识图谱的构建效率,最后通过建立基于行业schema的auto-KBQA((knowledge base question answering)解决领域知识图谱在知识问答应用的快速落地。通过实际项目的应用落地,验证了该框架可有效加快领域知识图谱的落地应用,期望该框架给领域知识图谱的快速构建和应用带来一定的启发和帮助。     

Temporal predicate transformers and fair termination

Summary It is usually assumed that implementations of nondeterministic programs may resolve the nondeterminacy arbitrarily. In some circumstances, however, we may wish to assume that the implementation is in some sense fair, by which we mean that in its long-term behaviour it does not show undue bias in forever favouring some nondeterministic choices over others. Under the assumption of fairness many otherwise failing programs become terminating. We construct various predicate transformer semantics of such fairly-terminating programs. The approach is based on formulating the familiar temporal operators always, eventually, and infinitely often as predicate transformers. We use these operators to construct a framework that accommodates many kinds of fairness, including varieties of socalled weak and strong fairness in both their all-levels and top-level forms. Our formalization of the notion of fairness does not exploit the syntactic shape of programs, and allows the familiar nondeterminacy and fair nondeterminacy to be arbitrarily combined in the one program. Invariance theorems for reasoning about fairly terminating programs are proved. The semantics admits probabilistic implementations provided that unbounded fairness is excluded.     

数据流程序动态调度与优化

为了解决数据流编程模型的可用性问题,使其能在兼顾程序并行性的前提下适用于动态数据交互速率的流应用,设计了一种动态调度与静态优化相结合的数据流编译系统。编译器以COStream语言编写的源程序为输入,通过对源程序进行分析,以动态速率的数据通信边作为边界划分程序到粗粒度的子图,在子图内部应用静态优化。根据子图的每个计算单元的工作量估计计算资源的使用状况,实现子图内计算单元到处理器核的映射,经过阶段划分分配子图内计算单元到相应流水阶段。在运行时,每个子图在各个处理器核上均启动一个线程,通过对线程间通信的优化,避免了运行时多个线程对同一段内存同时读写产生的同步开销,减少了线程的上下文切换次数。使用信号量控制子图内线程间的同步,基于各子图计算单元运行时数据交互速率并结合当前线程的状态,动态调度各个子图的执行,构建动态的软件流水线,生成相应多线程目标代码。实验以通用X86-64多核处理器作为实验平台,测试和分析数据流编译的性能。实验结果表明,编译系统可以实现动态数据交互速率的数据流应用,扩大了编译系统可用性并且具有一定加速效果。     

Teallach: a model-based user interface development environment for object databases

Model-based user interface development environments show promise for improving the productivity of user interface developers, and possibly for improving the quality of developed interfaces. While model-based techniques have previously been applied to the area of database interfaces, they have not been specifically targeted at the important area of object database applications. Such applications make use of models that are semantically richer than their relational counterparts in terms of both data structures and application functionality. In general, model-based techniques have not addressed how the information referenced in such applications is manifested within the described models, and is utilised within the generated interface itself. This lack of experience with such systems has led to many model-based projects providing minimal support for certain features that are essential to such data intensive applications, and has prevented object database interface developers in particular from benefiting from model-based techniques. This paper presents the Teallach model-based user interface development environment for object databases, describing the models it supports, the relationships between these models, the tool used to construct interfaces using the models and the generation of Java programs from the declarative models. Distinctive features of Teallach include comprehensive facilities for linking models, a flexible development method, an open architecture, and the generation of running applications based on the models constructed by designers.     

桌面环境下拼贴显示的自动对准

通过拼贴一组投影仪来构建高分辨率显示系统已成为现在一个较实际的办法.但是,这样的高分辨率显示系统用途有限,因为它们需要在定制的并行机或个人计算机集群上运行一些专门开发的并行形象化程序才能实现.针对个人计算机桌面环境下的任意拼贴显示给出了一种自动对准机制,使得桌面用户可以在其上运行普通的桌面应用软件.该系统包括3个步骤:检测投影仪对齐失准,计算出纠正所需之变换,对桌面环境进行实时的变形.这样就允许用户在运行任何2D,3D或视频程序时无须作任何修改,也无须使用专门的硬件支持.实验结果表明,系统能够获得亚像素级的精度,并且能在系统性能衰减最小的情况下达到实时变形.     

同步FTP上载／下载程序的实现技术

通常意义上的FTP（文件传输协议）客户程序都是指纯粹的异步上载／下载程序，但在实际应用开发中，FTP功能往往需要与特定的应用相结合，对于某些特殊的应用，通常的异步FTP程序设计方法不适用系统的需求，需要设计同步的FTP上载／下载程序，但开发工具如VB不提供直接的同步FTP支持。文章结合实际的系统开发，探讨了在特定应用中实现同步FTP上载／下载程序的方法和技术。     

Runtime and language support for compiling adaptive irregular programs on distributed-memory machines

In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed-memory message-passing machines, such as the Paragon, Delta, CM-5 and SP-1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high-level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real-life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle-in-cell code, DSMC. Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.     

A Deterministic Logical Semantics for Esterel

Esterel is a synchronous design language for the specification of reactive systems. There exist two main semantics for Esterel. On the one hand, the logical behavioral semantics provides a simple and compact formalization of the behavior of programs using SOS rules. But it does not ensure deterministic executions for all programs and all inputs. As non-deterministic programs have to be rejected as incorrect, this means it defines behaviors for incorrect programs, which is not convenient. On the other hand, the constructive semantics is deterministic (amongst other properties) but at the expense of a much more complex formalism. In this work, we construct and thoroughly analyze a new deterministic semantics for Esterel that retains the simplicity of the logical behavioral semantics, from which it derives. In our view, it provides a much better framework for formal reasoning about Esterel programs.