Software merge: Models and methods for combining changes to programs

We outline a model for programs and data and present a formal definition of an ideal change merging operation. This model is used to develop a new semantically based method for combining changes to programs. We also evaluate the appropriateness of the change merging operation and examine some circumstances where the specifications of a program as well as the implementations can be used to guide the change merging process in cases where the implementations conflict but the specifications do not. This work was performed for the Office of Naval Research and funded by the Naval Postgraduate School.     

Supporting intergenerational groups in computer-supported cooperative work (CSCW)

The workforce is ageing as older workers re-enter the workforce or delay retirement. One consequence is that work groups are increasingly becoming intergenerational. Because group work relies on many collaborative tools (e.g. email, shared calendars), it is essential to understand the special requirements that intergenerational groups have for groupware. Can we design collaborative tools that leverage the differing abilities and contributions of older and younger workers in groups? We focus on how best to support intergenerational groups, offering an analytical framework that combines ideas from the theory of small groups and activity theory. We consider design implications for computer-supported cooperative work (CSCW) and outline design principles for groupware that supports intergenerational groups. Finally, we discuss methodological issues that arise when studying intergenerational cooperative work.     

Development Support Tools for Enterprise Resource Planning

Implementing an enterprise system involves capturing all information necessary to make business processes work in an integrated fashion, and reflecting this integration in source code. Enterprise resource planning implementations should also exploit reuse of existing system elements. ERP tools typically work on top of a framework, using prefabricated modules to create customized variants of the system. Among the free and open source ERP systems, only ERP5 offers a comprehensive set of tools tailored to its framework that, together with other off-the-shelf tools, provide support for creating new modules and entire new systems.     

Using Verified Data-Flow Analysis-based Optimizations in Attribute Grammars

Building verified compilers is difficult, especially when complex analyses such as type checking or data-flow analysis must be performed. Both the type checking and program optimization communities have developed methods for proving the correctness of these processes and developed tools for using, respectively, verified type systems and verified optimizations. However, it is difficult to use both of these analyses in a single declarative framework since these processes work on different program representations: type checking on abstract syntax trees and data-flow analysis-based optimization on control flow or program dependency graphs.We present an attribute grammar specification language that has been extended with constructs for specifying attribute-labelled control flow graphs and both CTL and LTL-FV formulas that specify data-flow analyses. These formulas are model-checked on these graphs to perform the specified analyses. Thus, verified type rules and verified data-flow analyses (verified either by hand or with automated proof tools) can both be transcribed into a single declarative framework based on attribute grammars to build a high-confidence language implementations. Also, the attribute grammar specification language is extensible so that it is relatively straight-forward to add new constructs for different temporal logics so that alternative logics and model checkers can be used to specify data-flow analyses in this framework.     

From set membership to group membership: a separation of concerns

We revisit the well-known group membership problem and show how it can be considered a special case of a simple problem, the set membership problem. In the set membership problem, processes maintain a set whose elements are drawn from an arbitrary universe: They can request the addition or removal of elements to/from that set, and they agree on the current value of the set. Group membership corresponds to the special case where the elements of the set happen to be processes. We exploit this new way of looking at group membership to give a simple and succinct specification of this problem and to outline a simple implementation approach based on the state machine paradigm. This treatment of group membership separates several issues that are often mixed in existing specifications and/or implementations of group membership. We believe that this separation of concerns greatly simplifies the understanding of this problem.     

Pragmatic software configuration management

Often an organization's software configuration management (SCM) mechanisms don't help with the work of building software as much as they could. Either no mechanisms exist for doing common tasks or the processes to use those mechanisms are too complicated and become tasks in themselves. On a daily basis, developers shouldn't notice SCM that much, and what they do notice, they should eagerly embrace because these things help them do their jobs. When developers don't find SCM processes to be helpful, it's often because the processes don't serve the organization's goals well. This tends to be due to two issues: first, basic SCM structures lacking and, second, the structure doesn't fit well into the development environment. This paper provides a brief overview of the essential patterns for a basic, agile SCM environment.     

Designing business capability-aware configurable process models

Process Aware Information Systems manage processes within organisations on the basis of business process models. These models can be created either from scratch or by reusing exiting reference process models.Particular types of reference models are configurable process models that are created by merging multiple models into a single one that can be customized to the needs of the business experts. Using those models presents two main challenges: their creation and their configuration.In this paper, we focus on the first challenge and propose a novel algorithm for merging process models into a configurable process model. The difference in our work is the pre-annotated process models with their business capabilities that report on what actions each process element achieves. Our algorithm generates configurable models that are also annotated with their capabilities that can be used to face the second challenge of these models: the configuration phase.We tested our algorithm using real-world process models to evaluate the required creation time and resulting compression rate after merging the input models. The results show that the models can be created in few milliseconds and achieving a compression rate of 50%. We further carried out interviews with domain experts to assess the usefulness and the level of maturity of this work. The results show the importance of the automation of process merging using a tool support that we proposed. However, further adaptation efforts are required to integrate this work in the working environments of the interviewed experts.     

Making drilling operations visible: the role of articulation work for organisational safety

In the petroleum industry, new technologies and work processes are currently being developed as an innovation strategy for better, faster and safer drilling. In this article, some features of today’s work processes that contribute to successful operations are presented and discussed. The articulation work involved in handling the transient complexity of operations involves making black-boxed and invisible work processes visible and transparent. It is argued that this articulation work contributes to the organisation’s understanding and knowledge of the drilling processes and the dependencies that exist between different actors. In addition to contributing to ongoing problem solving, the articulation work also contributes to the awareness of possible future events. Following this insight, it is argued that efforts to improve operational efficiency and safety by introducing new tools and work processes should focus not only on the capability of new tools to support decisions and actions by instrumentation and automation, but attention should also be paid to the existing articulation work and its role in the accomplishment of work. In that way, the contributions of today’s articulation work can be strengthened instead of lost, and the outcome of the change processes can be even better than anticipated.     

Analysis of solutions to the time-optimal planning and execution problem

This paper analyses solutions to the time-optimal planning and execution (TOPE) problem, in which the aim is to minimise the total time required for an agent to achieve its objectives. The TOPE process provides a means of adjusting system parameters in real-time to achieve this aim. Prior work by the authors showed that agent-based planning systems employing the TOPE process can yield better performance than existing techniques, provided that a key estimation step can be run sufficiently fast and accurately. This paper describes several real-time implementations of this estimation step. A Monte-Carlo analysis compares the performance of TOPE systems using these implementations against existing state-of-the-art planning techniques. It is shown that the average case performance of the TOPE systems is significantly better than the existing methods. Since the TOPE process can be added to an existing system without modifying the internal processes, these results suggest that similar performance improvement may be obtained in a multitude of robotics applications.     

基于抽象语法树分析的版本控制分支合并算法

在软件开发中,并行开发已经成为了现实中标准的开发模式,因此软件开发的版本控制在开发过程中得到了非常广泛的应用.虽然大多数的版本控制工具都能完成分支合并以及将不同版本的更改合并起来,但这些工具往往是以一行一行的代码为单位进行文本比较的合并,在遇到某行被同时修改时,则不能给出满意的合并结果.给出了一种新的合并算法,用来解决文本比较分支合并中的问题,它在传统工具的文本比较出现冲突的代码行,对该代码块建立抽象语法树,根据抽象语法树的分析比较,完成不同分支版本代码的自动合并,减少分支合并中的代码冲突及手动合并的工作量,提高开发效率.     

Automating supply chains

A recent study found that supply-chain problems cost companies between 9 and 20 percent of their value over a six-month period (T.J. Becker, 2000). The problems range from part shortages to poorly utilized plant capacity. When you place this in the context of the overall business-to-business (B2B) market expected to reach US$7 trillion by 2004 (37 percent of which is projected to be e-commerce sales), it is easy to see that effective supply-chain management (SCM) tools could save companies billions of dollars. Attempts to automate solutions to these problems are complicated by the need for the different companies in a supply chain to maintain the integrity and confidentiality of their information systems and operations. The modeling technologies currently used within the manufacturing business-to-business standards communities, such as the Open Applications Group (http://www.openapplications.org) and RosettaNet (http://www.rosettanet.org) do a good job of capturing user requirements. Unfortunately, current technologies do not explicitly link the requirements to formal process models. This missing link is crucial to efficient SCM implementations     

A model-extraction approach to verifying concurrent C programs with CADP

The development of reliable software for industrial critical systems benefits from the use of formal models and verification tools for detecting and correcting errors as early as possible. Ideally, with a complete model-based methodology, the formal models should be the starting point to obtain the final reliable code and the verification step should be done over the high-level models. However, this is not the case for many projects, especially when integrating existing code. In this paper, we describe an approach to verify concurrent C code by automatically extracting a high-level formal model that is suitable for analysis with existing tools. The basic components of our approach are: (1) a method to construct a labeled transition system from the source code, that takes flow control and interaction among processes into account; (2) a modeling scheme of the behavior that is external to the program, namely the functionality provided by the operating system; (3) the use of demand-driven static analyses to make a further abstraction of the program, thus saving time and memory during its verification. The whole proposal has been implemented as an extension of the CADP toolbox, which already provides a variety of analysis modules for several input languages using labeled transition systems as the core model. The approach taken fits well within the existing architecture of CADP which does not need to be altered to enable C program verification. We illustrate the use of the extended CADP toolbox by considering examples of the VLTS benchmark suite and C implementations of various concurrent programs.     

Meetings of the Board: The Impact of Scheduling Medium on Long Term Group Coordination in Software Development

Despite a wealth of electronic group tools for coordinating the software development process, instead we find technologically adept groups preferring to use what seem to be outmoded material tools in critical projects. The current ethnographic study investigates this apparent paradox. We begin by building up a detailed picture of the overall software development process and identify critical general problems in achieving coordination. Coordination problems arise in software development not only because of the complex dependencies that hold among the work of different individuals, but also for social and motivational reasons. We identify the central role of the schedule as a coordination device, but find that its value can be undermined because the schedule is often neither accurate, current nor credible. As a result, the schedule is not used as a resource for individual or group planning. We then compare coordination in two development groups, one using electronic and the other material scheduling tools. We found that the medium of the schedule has a major impact on coordination problems. The size, public location and physical qualities of material tools engender certain crucial group processes that current electronic technologies fail to support. A large wallboard located in a public area encouraged greater responsibility, commitment and updating and its material properties served to encourage more reflective planning. As a result the wallboard schedule was both accurate and current. Furthermore, the public nature of the wallboard promoted group interaction around the board, it enabled collaborative problem solving, as well as informing individuals about the local and global progress of the project. Despite these benefits, however, the material tool fell short on several other dimensions such as distribution, complex dependency tracking, and versioning. We make design recommendations about how the benefits of material tools could be incorporated into electronic groupware systems and discuss the theoretical implications of this work.     

HPCVIEW: A Tool for Top-down Analysis of Node Performance

It is increasingly difficult for complex scientific programs to attain a significant fraction of peak performance on systems that are based on microprocessors with substantial instruction-level parallelism and deep memory hierarchies. Despite this trend, performance analysis and tuning tools are still not used regularly by algorithm and application designers. To a large extent, existing performance tools fail to meet many user needs and are cumbersome to use. To address these issues, we developed HPCVIEW—a toolkit for combining multiple sets of program profile data, correlating the data with source code, and generating a database that can be analyzed anywhere with a commodity Web browser. We argue that HPCVIEW addresses many of the issues that have limited the usability and the utility of most existing tools. We originally built HPCVIEW to facilitate our own work on data layout and optimizing compilers. Now, in addition to daily use within our group, HPCVIEW is being used by several code development teams in DoD and DoE laboratories as well as at NCSA.     

Comparing collaborative drawing tools and whiteboards: An analysis of the group process

Collaborative drawing tools, which are designed to allow multiple users to share an electronic drawing space, have recently become the focus of many researchers' efforts. While advances have been made in the technological implementation of these tools, little is known about the effect these tools have on group processes. This paper discusses a study that was conducted to compare groups using conventional (whiteboard) technology to those using collaborative drawing tools. The results of these two experiments provide evidence that these tools alter the way in, which groups work. For some types of tasks, the amount of interaction among group members using a collaborative drawing tool tends to be less than among groups using conventional technology. Groups using collaborative drawing tools tended to take significantly longer than whiteboard groups. Possible reasons for these results are further explored in this paper.     

Inference of regular languages using state merging algorithms with search

State merging algorithms have emerged as the solution of choice for the problem of inferring regular grammars from labeled samples, a known NP-complete problem of great importance in the grammatical inference area. These methods derive a small deterministic finite automaton from a set of labeled strings (the training set), by merging parts of the acceptor that corresponds to this training set. Experimental and theoretical evidence have shown that the generalization ability exhibited by the resulting automata is highly correlated with the number of states in the final solution.As originally proposed, state merging algorithms do not perform search. This means that they are fast, but also means that they are limited by the quality of the heuristics they use to select the states to be merged. Sub-optimal choices lead to automata that have many more states than needed and exhibit poor generalization ability.In this work, we survey the existing approaches that generalize state merging algorithms by using search to explore the tree that represents the space of possible sequences of state mergings. By using heuristic guided search in this space, many possible state merging sequences can be considered, leading to smaller automata and improved generalization ability, at the expense of increased computation time.We present comparisons of existing algorithms that show that, in widely accepted benchmarks, the quality of the derived solutions is improved by applying this type of search. However, we also point out that existing algorithms are not powerful enough to solve the more complex instances of the problem, leaving open the possibility that better and more powerful approaches need to be designed.     

HPCVIEW: A Tool for Top-down Analysis of Node Performance

It is increasingly difficult for complex scientific programs to attain a significant fraction of peak performance on systems that are based on microprocessors with substantial instruction-level parallelism and deep memory hierarchies. Despite this trend, performance analysis and tuning tools are still not used regularly by algorithm and application designers. To a large extent, existing performance tools fail to meet many user needs and are cumbersome to use. To address these issues, we developed HPCVIEW—a toolkit for combining multiple sets of program profile data, correlating the data with source code, and generating a database that can be analyzed anywhere with a commodity Web browser. We argue that HPCVIEW addresses many of the issues that have limited the usability and the utility of most existing tools. We originally built HPCVIEW to facilitate our own work on data layout and optimizing compilers. Now, in addition to daily use within our group, HPCVIEW is being used by several code development teams in DoD and DoE laboratories as well as at NCSA.     

‘You can dance your prototype if you like’: independent filmmakers adapting the hackathon

Hackathon-style events are increasingly used to facilitate cross-disciplinary learning and innovation in the media industries. Based on an observational study of a hackathon organized as part of the film festival Nordic Panorama (NP) we analyse the challenges in using the hackathon format to facilitate cross-disciplinary learning and innovation for filmmakers, developers and designers. We find that many participants experienced frustrations resulting from a lack of programming skills and their expectation that the hackathon should result in ‘something digital’. Additionally, ideals for authorship embedded in the working cultures of film and TV professionals impeded the team’s ability to involve all participants on an equal footing. As implications for future hackathons we suggest organizers should consider using tools for end-user development and generative toolkits to facilitate digital making and collaborative learning. We also suggest similar events should avoid including project owners if the group work is based on existing projects.     

From control law diagrams to Ada via Circus

Control engineers make extensive use of diagrammatic notations; control law diagrams are used in industry every day. Techniques and tools for analysis of these diagrams or their models are plentiful, but verification of their implementations is a challenge that has been taken up by few. We are aware only of approaches that rely on automatic code generation, which is not enough assurance for certification, and often not adequate when tailored hardware components are used. Our work is based on Circus, a notation that combines Z, CSP, and a refinement calculus, and on industrial tools that produce partial Z and CSP models of discrete-time Simulink diagrams. We present a strategy to translate Simulink diagrams to Circus, and a strategy to prove that a parallel Ada implementation refines the Circus specification; we rely on a Circus semantics for the program. By using a combined notation, we provide a specification that considers both functional and behavioural aspects of a large set of diagrams, and support verification of a large number of implementations. We can handle, for instance, arbitrarily large data types and dynamic scheduling.     

On the roles of policies in computer systems management

Policies are a pervasive and critical aspect of computer system management. What makes an effective policy? How do policies work in practice? To what extent can policy specification and implementation be formalized and automated? We studied the work practices of computer system administrators to uncover some of the ways policies are used in practice, and to inform the design of tools that incorporate policies to support more effective system management. We found that polices come in many forms—documented in service-level agreements and best-practice guidelines, given by management directives, applied by system administrators through formal processes, and built into tools such as configuration management applications. We found that although policies sometimes make explicit statements and establish formal processes, much is left implicit, by design or omission, with appropriate interpretation and execution dependent on human judgment. We argue that people must play an active role in the application of policies to system management because complex situational demands require it, and we discuss some issues in the design of tools that incorporate policies in supporting computer system management.