Technical Reports

The ICICS/CS Reading Room

2002 UBC CS Technical Report Abstracts

TR-2002-01 Understanding Design Patterns with Design Rationale Graphs, March 01, 2002 Elisa L. A. Baniassad, Gail C. Murphy and Christa Schwanninger, 8 pages

A Design Pattern presents a proven solution to a common design problem using a combination of informal text, diagrams, and examples. Often, to suitably describe an issue, the author of a Design Pattern must spread and repeat information throughout the Pattern description. Unfortunately, spreading the information can make it difficult for a reader to grasp subtleties in the design, leading to possible misuses of the Pattern. In this paper, we introduce the Design Rationale Graph (DRG) representation that connects and visualizes related concepts described in a Design Pattern. The localization of concept information is intended to help improve a reader\222s understanding of a Design Pattern. Improved comprehension of a Pattern could aid the use of a Pattern during implementation, and the reading of code built upon the Pattern. In addition to describing the DRG representation, we present a tool we have built to support the semi-automatic creation of a DRG from Design Pattern text, and we report on a small study conducted to explore the utility of DRGs. The study showed that readers with access to a DRG were able to answer questions about the Pattern more completely and with more confidence than those given the Design Pattern alone.

TR-2002-02 Proceedings of the First AOSD Workshop on Aspects, Components, and Patterns for Intrastructure Software, April 23, 2002 Yvonne Coady (Ed.), 85 pages

Aspect-oriented programming, component models, and design patterns are modern and actively evolving techniques to improving the modularization of complex software. In particular, these techniques hold great promise for the development of "systems infrastructure" software, e.g., application servers, middleware, virtual machines, compilers, operating systems, and other software that provides general services for higher-level applications. The developers of infrastructure software are currently faced with increasing demands from application programmers needing higher-level support for application development. Meeting these demands requires careful use of software modularization techniques, since infrastructural concerns are notoriously hard to modularize. Aspects, components, and patterns provide very different means to deal with infrastructure software, but despite their differences, they have much in common. For instance, component models try to free the developer from the need to deal directly with services like security or transactions. These are primary examples of crosscutting concerns, and modularizing such concerns are the main target of aspect-oriented languages. Similarly, design patterns like Visitor and Interceptor facilitate the clean modularization of otherwise tangled concerns. This workshop aims to provide a highly interactive forum for researchers and developers to discuss the application of and relationships between aspects, components, and patterns within modern infrastructure software. The goal is to put aspects, components, and patterns into a common reference frame and to build connect ions between the software engineering and systems communities.

TR-2002-03 Motion Perturbation Based on Simple Neuromotor Control Models, May 23, 2002 Michael B. Clien, KangKang Yin and Dinesh K. Pai, 8 pages

Motion capture is widely used for character animation. One of the major challenges in this area is modifying human motion in plausible ways. Previous work has focused on transformations based on kinematics and dynamics, but has not explicitly taken into account the emerging knowledge of how humans control their motion. In this paper we show how this can be done using a simple human neuromuscular control model. Our model of muscle forces includes a feedforward term and low gain passive feedback. The feedforward component is calculated from motion capture data using inverse dynamics. The feedback component generates reaction forces to unexpected external disturbances. The perturbed animation is then resynthesized using forward dynamics. This allows us to create animations where the character reacts to unexpected external forces in a natural way (e.g.,when the character is hit by a flying object), but still retains qualities of the original animation. Such technique is useful for applications such as interactive sports video games.

TR-2002-04 The Inequalities of Quantum Information Theory, May 28, 2002 Nicholas Pippenger, i+46 pages

The Inequalities of Quantum Information Theory Nicholas Pippenger Given an n-part quantum state, we consider the 2^n substates obtained by restricting attention to a subset of the parts. The entropies (in the sense of von Neumann) of these substates may be regarded as a point, called the allocation of entropy, in a (2^n)-dimensional real vector space. We show that the topological closure of the set of allocations of entropy form a convex cone. We show that a set of inequalities due to Lieb and Ruskai characterize this cone when n is at most 3. We also consider the symmetric situation in which the entropy depends only on the number of parts in the substate. In this case, the topological closure of the set of allocations of entropy (in (n+1)-dimensional space) again form a convex cone, and we give inequalities characterizing this cone for all n.

TR-2002-05 Scaling an Object-Oriented System Execution Visualizer Through Sampling, December 11, 2002 Andrew Chan, Reid Holmes, Gail C. Murphy and Annie T.T. Ying, 11 pages

Increasingly, applications are being built by combining existing software components. For the most part, a software developer can treat the components as black-boxes. However, for some tasks, such as when performance tuning, a developer must consider how the components are implemented and how they interact. In these cases, a developer may be able to perform the task more effectively by using dynamic information about how the system executes. In previous work, we demonstrated the utility of a tool, called AVID (Architectural VIsualization of Dynamics), that animates dynamic information in terms of developer-chosen architectural views. One limitation of this earlier work was that AVID relied on trace information collected about the system's execution, limiting the duration of execution that could be considered. To enable AVID to scale to larger, longer-running systems, we have been investigating the visualization and animation of sampled dynamic information. In this paper, we discuss the addition of sampling support to AVID, and we present two case studies in which we experimented with animating sampled dynamic information to help with performance tuning tasks.

TR-2002-06 Entropy and Expected Acceptance Counts for Finite Automata, September 03, 2002 Nicholas Pippenger, 24 pages

Entropy and Expected Acceptance Counts for Finite Automata Nicholas Pippenger If a sequence of independent unbiased random bits is fed into a finite automaton, it is straightforward to calculate the expected number of acceptances among the first n prefixes of the sequence. This paper deals with the situation in which the random bits are neither independent nor unbiased, but are nearly so. We show that, under suitable assumptions concerning the automaton, if the the difference between the entropy of the first n bits and n converges to a constant exponentially fast, then the change in the expected number of acceptances also converges to a constant exponentially fast. We illustrate this result with a variety of examples in which numbers following the reciprocal distribution, which governs the significands of floating-point numbers, are recoded in the execution of various multiplication algorithms.

TR-2002-07 Extended Canonical Recoding, September 05, 2002 Nicholas Pippenger

Canonical recoding transforms a sequence of bits into a sequence of signed digits, preserving the numerical value of the sequence while reducing the number of non-zero digits. It is used to reduce the number of additions and subtractions when performing multiplication (or equivalently, the number of multiplications and divisions when performing exponentiation). Standard canonical recoding uses the digits 0, 1 and -1. Any two non-zero digits are separated by at least one zero, so in the worst case n/2 + O(1) non-zero digits are used to recode an n-bit sequence; in the average case n/3 + O(1) non-zero digits are used. We introduce extended canonical recoding, which uses the digits 0, 1, -1, 3 and -3. Any two non-zero digits are separated by at least two zeroes, so at most n/3 + O(1) non-zero digits are used in the worst case. We show that the scheme is uniquely determined by this condition, and that it is optimal among schemes using the same set of signed digits. Finally, we show that in the average case, extended canonical recoding uses n/4 + O(1) non-zero digits.

TR-2002-08 Choosing the Right Neighbourhood: a Way to Improve a Stochastic Local Search Algorithm, October 10, 2002 D. C. Tulpan and H. Hoos, 15 pages

for DNA Word Design algorithm for the design of DNA codes, namely sets of equal-length words over the nucleotides alphabet $\{A,C,G,T\}$ that satisfy certain combinatorial constraints. Using empirical analysis of the algorithm, we gain insight on good design principles and in turn improve the performance of the SLS algorithm. We report several cases in which our algorithm finds word sets that match or exceed the best previously known constructions.

TR-2002-11 Back to the Future: A Retroactive Study of Aspect Evolution in Operating System Code, October 21, 2002 Yvonne Coady and Gregor Kiczales, 10 pages

The FreeBSD operating system more than doubled in size between version 2 and version 4. Many changes to primary modularity are easy to spot at a high-level. For example, new device drivers account for 38% of the growth. Not surprisingly, changes to crosscutting concerns are more difficult to track. In order to better understand how an aspect-oriented implementation would have fared during this evolution, we introduced several aspects to version 2 code, and then rolled them forward into their subsequent incarnations in versions 3 and 4 respectively. This paper describes the impact evolution had on these concerns, and provides a comparative analysis of the changes required to evolve the original versus aspect-oriented implementations. Our results show that for the concerns we chose, the aspect-oriented implementation facilitated evolution in four key ways: (1) changes were better localized, (2) configurability was more explicit, (3) redundancy was reduced, and (4) extensibility aligned with an aspect was more modular. Additionally, we found the aspect-oriented implementation had negligible impact on performance.

If you have any questions or comments regarding this page please send mail to