• J. Chen and S. MacDonald, "Towards a Better Collaboration of Static and Dynamic Analyses for Testing Concurrent Programs", in Proceedings of the 2008 Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD 2008), Seattle, WA, July 2008. 9 ms.
  (Abstract, .ps.gz, .pdf)
• A. Stevenson and S. MacDonald, "Dynamic Aspect-Oriented Load Balancing in Java RMI", in Proceedings of the 2008 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2008), Las Vegas, NV, July 2008, pages 485-491.
  (Abstract, .ps.gz, .pdf)
• W. van Heiningen, S. MacDonald, and T. Brecht, "Babylon: Middleware for Distributed, Parallel, and Mobile Java Applications", Concurrency and Computation: Practice and Experience 20(10):1195-1224, 2008.
  (Abstract, .ps.gz, .pdf)
• A. Stevenson and S. MacDonald, "Smart Proxies in Java RMI with Dynamic Aspect-Oriented Programming", in Proceedings of the 10th International Workshop on Java and Components for Parallelism, Distribution, and Concurrency (IWJPDC 2008), Miama, FL, April 2008. 6 ms.
  (Abstract, .ps.gz, .pdf)

• J. Chen and S. MacDonald, "Testing Concurrent Programs using Value Schedules", in Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2007), Atlanta, GA, November 2007, pages 313-322.
  (Abstract, .ps.gz, .pdf)
• S. MacDonald, K. Tan, J. Schaeffer, and D. Szafron, "Deferring Design Pattern Decisions and Automating Structural Pattern Changes using a Design-Pattern-Based Programming System", accepted to ACM Transactions on Programming Languages and Systems, June 2007. 45 ms.
  (Abstract, .ps.gz, .pdf)

• S. MacDonald, J. Chen, and D. Novillo, "Deterministically Executing a Concurrent Program for Testing and Debugging", in Proceedings of the 2006 International Conference on Programming Languages and Compilers (PLC 2006), Las Vegas, NV, June 2006, pages 844-850.
  (Abstract, .ps.gz, .pdf)
• J. Chen and S. MacDonald, "Exploiting Roles and Responsibilities to Generate Code in a Distributed Design-Pattern-Based Programming System", in Proceedings of the 2006 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2006), Las Vegas, NV, June 2006, pages 17-23.
  (Abstract, .ps.gz, .pdf)
• W. van Heiningen, T. Brecht, and S. MacDonald, "Exploiting Dynamic Proxies in Middleware for Distributed, Parallel, and Mobile Java Applications", in Proceedings of the 8th International Workshop on Java for Parallel and Distributed Computing (JAVAPDC 2006), Rhodes Island, Greece, April 2006. 8 ms.
  (Abstract, .ps.gz, .pdf)
• W. van Heiningen, T. Brecht, and S. MacDonald, "Babylon v2.0: Middleware for Distributed, Parallel, and Mobile Java Applications", in Proceedings of the 11th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS 2006), Rhodes Island, Greece, April 2006. 8ms.
  (Abstract, .ps.gz, .pdf)

• S. MacDonald, J. Chen, and D. Novillo, "Choosing Among Alternative Futures", in Proceedings of First International Haifa Verification Conference, Haifa, Israel, November 2005, Volume 3875 of Lecture Notes in Computer Science, pages 247-264.
  (Abstract, .ps.gz, .pdf)
• J. Chen and S. MacDonald, "RoadMapAssembler: A New Pattern-Based J2EE Development Tool", in Proceedings of CASCON 2005, Toronto, Ontario, Canada, October 2005, pages 113-127.
  (Abstract, .ps.gz, .pdf)
• S. MacDonald, "Transforming an Object-Oriented Pipeline to a Master-Worker: The State-Based Pipeline ", Design pattern workshopped at the First Workshop on Patterns in High Performance Computing (patHPC 2005), Urbana-Champaign, IL, May 2005, 9 pp.
  (Description, .ps.gz, .pdf)

• S. MacDonald, D. Szafron, and J. Schaeffer, "Rethinking the Pipeline as Object-Oriented States with Tranformations", In Proceedings of the 9th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS 2004), Santa Fe, NM, April 2004, pages 12-21.
  (Abstract, .ps.gz, .pdf)

• K. Tan, D. Szafron, J. Schaeffer, J. Anvik, and S. MacDonald, "Using Generative Design Patterns to Generate Parallel Code for a Distributed Memory Environment", in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2003), San Diego, CA, June 2003, pages 203-215.
  (Abstract, .pdf)

• S. MacDonald, J. Anvik, S. Bromling, J. Schaeffer, D. Szafron, and K. Tan, "From Patterns to Frameworks to Parallel Programs", Parallel Computing, 28(12):1663-1683, 2002.
  (Abstract, .ps.gz, .pdf)
• S. MacDonald, D. Szafron, J. Schaeffer, J. Anvik, S. Bromling and K. Tan, "Generative Design Patterns", in Proceedings of the 17th International Conference on Automated Software Engineering (ASE2002), Edinburgh, UK, September 2002, pages 23-34.
  (Abstract, .pdf)
• S. Bromling, S. MacDonald, J. Anvik, J. Schaeffer, D. Szafron, and K. Tan, "Pattern-based Parallel Programming", in Proceedings of the 2002 International Conference on Parallel Processing (ICPP2002), Vancouver, British Columbia, August 2002, pages 257-265.
  (Abstract, .pdf)
• J. Anvik, S. MacDonald, D. Szafron, J. Schaeffer, S. Bromling and K. Tan, "Generating Parallel Programs from the Wavefront Design Pattern", in Proceedings of the 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS'02) (CD-ROM), Fort Lauderdale, Florida, April 2002, 8 pages. Awarded Best Paper of the workshop.
  (Abstract, .pdf)

• S. MacDonald, "From Patterns to Frameworks to Parallel Programs", Ph.D. Thesis, Department of Computing Science, University of Alberta, November 2001. Also listed as Technical Report TR02-02, Department of Computing Science, University of Alberta, January 2002.
  (Abstract, .ps.gz, .pdf)

• W. Hui, S. MacDonald, J. Schaeffer, and D. Szafron, "Visualizing Object and Method Granularity for Program Parallelization", in Proceedings of Parallel and Distributed Computing and Systems (PDCS 2000), Las Vegas, Nevada, November 2000, pages 286-291.
  (Abstract, .pdf)
• S. MacDonald, "Two-Dimensional Mesh Design Pattern Template for CO2P3S", Research document, October 2000.
  (Abstract, .ps.gz)
• S. MacDonald, D. Szafron, J. Schaeffer, and S. Bromling, "Generating Parallel Program Frameworks from Parallel Design Patterns", in Proceedings of the 6th International Euro-Par Conference (Euro-Par 2000), Munich, Germany, August 2000, Lecture Notes in Computer Science 1900, Springer-Verlag, pages 95-104.
  (Abstract, .ps.gz)

• S. MacDonald, D. Szafron, and J. Schaeffer, "Object-Oriented Pattern-Based Parallel Programming with Automatically Generated Frameworks", in Proceedings of the 5th USENIX Conference on Object-Oriented Tools and Systems (COOTS'99), San Diego, CA, May 1999, pages 29-43.
  (Abstract, .ps.gz, HTML)

• S. MacDonald, "Pattern-based Object-Oriented Parallel Programming", Candidacy document, University of Alberta, January 1998.
  (.ps.gz)

• S. MacDonald, J. Schaeffer, and D. Szafron, "Pattern-based Object-Oriented Parallel Programming", in Proceedings of the First International Scientific Computing in Object-Oriented Parallel Environments Conference (ISCOPE '97), Marina del Rey, California, USA, December 1997, Lecture Notes in Computer Science 1343, Springer-Verlag, pages 267-274.
  (Abstract, Extended Abstract (.ps.gz), Paper (.ps.gz))

• S. MacDonald, "Design Patterns in Enterprise", In CASCON '96 CD-ROM Proceedings, Toronto, Ontario, Canada, November 1996.
  (Abstract, .ps.gz)
• S. MacDonald, D. Szafron, J. Schaeffer, "An Object-Oriented Run-time System for Parallel Applications", In Proceedings of Technology of Object-Oriented Languages and Systems (TOOLS) USA '96, Santa Barbara, CA, USA, August 1996.
  (Abstract, .ps.gz)
• P. Iglinski, N. Kazouris, S. MacDonald, D. Novillo, I. Parsons, J. Schaeffer, D. Szafron, and D. Woloschuk, "Using a Template-Based Parallel Programming Environment to Eliminate Errors", In Proceedings of the 1996 High Performance Computing Symposium, Ottawa, Ontario, Canada, June 1996.
  (Abstract, .ps.gz)

• D. Woloschuk, P. Iglinski, S. MacDonald, D. Novillo, I. Parsons, J. Schaeffer, and D. Szafron, "Performance Debugging in the Enterprise Parallel Programming Environment", In CASCON '95 CD-ROM Proceedings, Toronto, Ontario, Canada, November 1995.
  (Abstract, .ps.gz)
• S. MacDonald, "An Object-Oriented Run-time System for Parallel Programming", Master's Thesis, Department of Computing Science, University of Alberta, October 1995.
  (Abstract, .ps.gz)
• P. Iglinski, S. MacDonald, C. Morrow, D. Novillo, I. Parsons, J. Schaeffer, D. Szafron, and D. Woloschuk. "Enterprise User's Manual Version 2.4", Technical Report TR95-02, Department of Computing Science, University of Alberta, January 1995.
  (Abstract, .ps.gz)

J. Chen and S. MacDonald, "Towards a Better Collaboration of Static and Dynamic Analyses for Testing Concurrent Programs", in Proceedings of the 2008 Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD 2008), Seattle, WA, July 2008. 9 ms.

Testing concurrent programs remains a difficult task due to the non-deterministic nature of concurrent executions. Many approaches have been proposed to combine static and dynamic analysis to reduce the complexity of uncovering potential concurrency bugs. However, the existing collaboration schemes only provide a limited mechanism for exchanging relevant information between the two analyses. For example, alias information only flows from the static analysis module to the dynamic analysis module at the beginning of the dynamic analysis. Therefore, we cannot fully exploit the advantages of each type of analysis. Motivated by this observation, in this paper we present a new testing technique which enables a tighter collaboration between static analysis and dynamic analysis. In this collaboration scheme, static analysis and dynamic analysis interact iteratively throughout the whole testing process. Static analysis uses coarse-grained analysis to guide the dynamic analysis to concentrate on the relevant search space, while dynamic analysis collects concrete runtime information during the guided exploration. The runtime information provided by the dynamic analysis helps the static analysis to refine its coarse-grained analysis and provides better guidance on dynamic analysis. Currently, our implementation consists of a static analysis module based on Soot and a dynamic analysis module based on JPF (Java PathFinder).

A. Stevenson and S. MacDonald, "Dynamic Aspect-Oriented Load Balancing in Java RMI", in Proceedings of the 2008 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2008), Las Vegas, NV, July 2008, pages 485-491.

Load balancing is the process of distributing client requests over a set of servers, and is a key element of obtaining good performance in a distributed application. Java RMI extends Java with distributed objects whose methods can be called from remote clients. In some Java RMI programs, there may be multiple replicas of a given object that can be the receiver of a remote method invocation. Effectively distributing these requests across these replicas requires either an extra balancer process or additional code on the client for this distribution. In this paper, we demonstrate the use of dynamic aspects in JAC to solve this problem. The client proxy is modified with an aspect to forward requests to a specific server, but the server is also able to shed load by altering or removing this aspect. The overhead of this approach is evaluated using a set of microbenchmarks.

A. Stevenson and S. MacDonald, "Smart Proxies in Java RMI with Dynamic Aspect-Oriented Programming", in Proceedings of the 10th International Workshop on Java and Components for Parallelism, Distribution, and Concurrency (IWJPDC 2008), Miama, FL, April 2008. 6 ms.

Java RMI extends Java with distributed objects whose methods can be called from remote clients. This abstraction is supported using statically-generated proxy objects on the client to hide network communication. One limitation of Java RMI is that these proxies can only forward method calls from client to server. Many applications can benefit from smart proxies that shift some application responsibilities to the client. Normally, developers must manually implement such proxies. This paper describes an aspect-oriented approach to creating smart proxies. This approach allows a server to extend an existing proxy with new capabilities at runtime. This approach is demonstrated with two examples.

J. Chen and S. MacDonald, "Testing Concurrent Programs using Value Schedules", in Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2007), Atlanta, GA, November 2007, pages 313-322.

Concurrent programs are difficult to debug and verify because of the nondeterministic nature of concurrent executions. A particular concurrency-related bug may only show up under certain rarely-executed thread interleavings. Therefore, commonly used debugging methodologies, such as inserting print statements, are no longer sufficient for uncovering concurrency-related bugs. However, many existing bug detection methods, such as dynamic analysis and model checking, have a very high computational cost.

In this paper, we introduce a new technique for uncovering concurrency-related bugs from multithreaded Java programs. Our technique uncovers concurrency-related bugs by generating and testing read-write assignment sequences, referred to as value schedules, of a multithreaded Java program. Our value-schedule-based technique distinguishes itself in its ability to avoid exploring superfluous program state space caused by speculative permutation on transitions. Therefore, our technique can achieve a higher degree of POR (Partial Order Reduction) than existing methods. We demonstrate our technique using some programs, with an implementation built using an explicit state model checker called JPF.

W. van Heiningen, S. MacDonald, and T. Brecht, "Babylon: Middleware for Distributed, Parallel, and Mobile Java Applications", Concurrency and Computation: Practice and Experience 20(10):1195-1224, 2008.

Babylon is a collection of tools and services that provide a 100% Java compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features like object migration, asynchronous method invocation and remote class loading while providing an easy-to-use interface. Additionally, Babylon enables Java applications to seamlessly create and interact with remote objects while protecting those objects from other applications by implementing access restrictions and separate namespaces.

The implementation of Babylon centers around dynamic proxies, a feature first available in Java 1.3, that allows proxy objects to be created at runtime. Dynamic proxies play a key role in achieving the goals of Babylon.

The potential cluster computing benefits of the system are demonstrated with experimental results which show that sequential Java applications can achieve significant performance benefits from using Babylon to parallelize their work across a cluster of workstations.

S. MacDonald, K. Tan, J. Schaeffer, and D. Szafron, "Deferring Design Pattern Decisions and Automating Structural Pattern Changes using a Design-Pattern-Based Programming System", accepted to ACM Transactions on Programming Languages and Systems, June 2007. 45 ms.

In the design phase of software development, the designer must make many fundamental design decisions concerning the architecture of the system. Incorrect decisions are relatively easy and inexpensive to fix if caught during the design process, but the difficulty and cost rise significantly if problems are not found until after coding begins. Unfortunately, it is not always possible to find incorrect design decisions during the design phase. To reduce the cost of expensive corrections, it would be useful to have the ability to defer some design decisions as long as possible, even into the coding stage. Failing that, tool support for automating design changes would give more freedom to revisit and change these decisions when needed. This paper shows how a design-pattern-based programming system based on generative design patterns can support the deferral of design decisions where possible, and automate changes where necessary. A generative design pattern is a parameterized pattern form that is capable of generating code for different versions of the underlying design pattern. We demonstrate these ideas in the context of a parallel application written with the CO2P3S pattern-based parallel programming system. We show that CO2P3S can defer the choice of execution architecture (shared-memory or distributed-memory), and can automate several changes to the application structure that would normally be daunting to tackle late in the development cycle. Although we have done this work with a pattern-based parallel programming system, it can be generalized to other domains.

Non-determinism is a serious problem in the testing and debugging of concurrent programs. Thread interleavings may be different on each run, changing the order of events. Testing a concurrent program requires many of these orders to be run, either to determine that all orders produce correct results or to identify the presence of timing-dependent errors called race conditions. This paper presents preliminary work in deterministically executing a concurrent program using a combination of an intermediate compiler form and aspect-oriented programming. Specifically, we execute the code generated for the intermediate compiler form using aspects to control the value returned for the read of any shared variable. This allows us to deterministically execute specific test cases. This work is preliminary, with many outstanding issues, but we feel the technique shows promise.

The implementation of a design pattern can be viewed as a process of selecting classes to play the roles needed by the pattern. To ensure that a class can play a role, each role has a set of responsibilities associated with it. When all responsibilities are satisfied, the pattern implementation is complete. Normally a programmer must write code for the responsibilities. However, the implementation of responsibilities can often be derived from information in the application or from user input, and then automatically generated. This paper describes a new approach that uses roles and responsibilities to generate code for an almost-complete application architecture in a pattern-based framework, leaving only application-specific code for the developer. We demonstrate this approach using RMA, an Eclipse plugin for writing Java 2 Enterprise Edition (J2EE) applications based on an existing J2EE framework.

Babylon v2.0 is a collection of tools and services that provide a 100% Java compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features like object migration, asynchronous method invocation and remote class loading while providing an easy-to-use interface. The implementation of Babylon v2.0 exploits dynamic proxies, a feature added to Java 1.3 that allows runtime creation of proxy objects. This paper shows how Babylon v2.0 exploits dynamic proxies to implement several key features without the need for special language or virtual machine extensions, preprocessors, or compilers. The resulting Babylon programs are portable across all Java virtual machines, and the development process is simplified by removing the extra steps needed to invoke external stub compilers and incorporate the generated code into an application. This simplification also allows remote objects to be created for any class that supports an interface to its methods, even if source code is not available.

Babylon v2.0 is a collection of tools and services that provide a 100% Java compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features like object migration, asynchronous method invocation and remote class loading while providing an easy-to-use interface. Additionally, Babylon v2.0 enables Java applications to seamlessly create and interact with remote objects while protecting those objects from other applications by implementing access restrictions and separate name spaces.

This paper describes the most important programming features of the Babylon v2.0 system, using a heat diffusion example to show how they are used in practice. The potential cluster computing benefits of the system are demonstrated with experimental results which show that sequential Java applications can achieve significant performance benefits from using Babylon v2.0 to parallelize their work across a cluster of workstations.

Non-determinism is a serious impediment to testing and debugging concurrent programs. Such programs do not execute the same way each time they are run, which can hide the presence of errors. Existing techniques use a variety of mechanisms that attempt to increase the probability of uncovering error conditions by altering the execution sequence of a concurrent program, but do not test for specific errors. This paper presents some preliminary work in deterministically executing a multithreaded program using a combination of an intermediate compiler form that identifies concurrent reaching definitions and aspect-oriented programming to control program execution. Specifically, the aspects allow a read of a shared variable to return any of the reaching definitions, where the desired definition can be selected before the program is run. As a result, we can deterministically run test cases. This work is preliminary and many issues have yet to be resolved, but we believe this idea shows some promise.

The quality of a J2EE web application depends on both the correctness of the code as well as the efficiency and flexibility of its architecture. Unfortunately, the design and development process is complex and includes tedious coding details, making it error-prone. Part of the problem lies in the incomplete abstractions provided by the J2EE specification. The artifacts of the distributed system environment are still present in applications and cannot be ignored, notably interfaces for distributed objects, name space information, and deployment information. In this paper, we present the detailed design of our design-pattern-based J2EE development system, RoadMapAssembler. This system shows that a J2EE architectural framework can be generated by assembling a set of design patterns in an incremental fashion, exploiting our knowledge of pattern implementations and inter-pattern relationships. This same knowledge also allows us to generate code for the distributed system artifacts that pollute J2EE applications. We demonstrate these features through the development of an example J2EE application.

However, expert parallel programmers typically eschew using the pipeline structure, especially for coarse-grained applications. The pipeline suffers from three serious problems that make an efficient and flexible implementation difficult. First, processors are idle when the pipeline is not full. This happens when the pipeline starts filling up (ramp-up time) and when there are no more input requests and the pipeline is emptying (ramp-down time). Second, traditional pipeline implementations are sensitive to load imbalance. Obtaining the best possible performance requires that the computation for each stage be perfectly balanced. Otherwise, stages that require less computation will be idle, waiting for work from more expensive stages. Third, traditional pipeline implementations tightly couple the concurrency with the computational stages. Each thread is assigned to execute a specific part of the computation. This makes it difficult to incrementally add new processors while still maintaining the balance among stages for good performance.

The problem addressed in this pattern is how to formulate a more efficient pipeline implementation that either reduces or eliminates these problems. In doing so, programmers may be more willing to use pipelines to solve their problems. They can take advantage of conceptual simplicity of this common parallel structure rather than being forced to rethink the problem because of the limitations of pipeline implementations.

Parallel programming offers potentially large performance benefits for computationally intensive problems. Unfortunately, it is difficult to obtain these benefits because parallel programs are more complex than their sequential counterparts. One way to reduce this complexity is to use a parallel programming system to write parallel programs. This dissertation shows a new approach to writing object-oriented parallel programs based on design patterns, frameworks, and multiple layers of abstraction. This approach is intended as the basis for a new generation of parallel programming systems.

A critical evaluation of existing parallel programming systems is presented. This evaluation is based on a set of 13 characteristics of an ideal pattern-based parallel programming system. Based on the results of this evaluation, the PDP process was created. This process provides multiple layers of abstraction to support the complete application development cycle. The first layer supports pattern-based parallel programming by generating object-oriented frameworks from a design pattern description of the application structure. The generated code is hidden from the user to ensure correctness. Lower layers gradually provide access to the generated structural code and other low-level facilities.

The CO2P3S parallel programming system is an example of a tool that supports the PDP process. It generates multithreaded Java frameworks for a set of supported design pattern templates. The utility of this tool is demonstrated by four example programs which obtain reasonable speedups after being written using CO2P3S. Further, the results of a usability experiment are presented. The experiment compared parallel programming using CO2P3S against programming in non-CO2P3S Java with threads. The results show that CO2P3S users write less application code than their Java counterparts, and that this code is less complex.

Enterprise is an integrated parallel programming system that provides facilities to create, compile, execute, tune, and debug parallel programs on a network of workstations. Enterprise uses two models to completely specify a program. The first model presents an abstraction that relates the different elements of a program to assets in a business enterprise, giving an intuitive method of expressing the parallelism in the program. The second model modifies the semantics of sequential C so that the assets are called remotely. This last model is implemented by preprocessing the user's code to invoke the run-time system, which handles message passing and synchronization.

This thesis proposes that the run-time system can be designed and implemented using object-oriented techniques to improve upon specific aspects of the previous version. Most of these changes fix known limitations or errors in the previous system. The new system is more flexible, allowing the programming models to be changed easily. It can also dynamically incorporate new resources into an executing program. The preprocessing stage has been simplified and, finally, the communications system was abstracted out of the code. These changes, along with several other optimizations, have been implemented and the new and old systems were compared. The results show that the new system has met all of its goals, although some have yet to be validated.