To achieve high performance on multi-cores, modern loop optimizers apply long sequences of transformations that produce complex loop structures. Downstream optimizations such as register tiling (unroll-and-jam plus scalar promotion) typically provide a significant performance improvement. Typical register tilers provide this performance improvement only when applied on simple loop structures. They often fail to operate on complex loop structures leaving a significant amount of performance on the table. We present a technique called compact multi-dimensional kernel extraction (COMDEX) which can make register tilers operate on arbitrarily complex loop structures and enable them to provide the performance benefits. COMDEX extracts compact unrollable kernels from complex loops. We show that by using COMDEX as a pre-processing to register tiling we can (i) enable register tiling on complex loop structures and (ii) realize a significant performance improvement on a variety of codes.

Layered queues are a canonical form of extended queueing network for systems with nested multiple resource possession, in which successive depths of nesting define the layers. The model has been applied to most modern distributed systems, which use different kinds of client-server and master-slave relationships, and scales up well. The layered queueing network (LQN) model is described here in a unified fashion, including its many more extensions to match the semantics of sophisticated practical distributed and parallel systems. These include efficient representation of replicated services, parallel and quorum execution, and dependability analysis under failure and reconfiguration. The full LQN model is defined here and its solver is described. A substantial case study to an air traffic control system shows errors (compared to simulation) of a few percent. The LQN model is compared to other models and solutions, and is shown to cover all their features.

Continuous-time Markov chains (CTMCs) have been used successfully to model the dependability and performability of many systems. Matrix diagrams (MDs) are known to be a space-efficient, symbolic representation of large CTMCs. In this paper, we identify local conditions for exact and ordinary lumpings that allow us to lump MD representations of Markov models in a compositional manner. We propose a lumping algorithm for CTMCs that are represented as MDs that is based on partition refinement, is applied to each level of an MD directly, and results in an MD representation of the lumped CTMC. Our compositional lumping approach is complementary to other known model-level lumping approaches for matrix diagrams. The approach has been implemented, and we demonstrate its efficiency and benefits by evaluating an example model of a tandem multi-processor system with load balancing and failure and repair operations.

Functional Interface (AFI). Models and solution techniques interact with one another through the use of the standard interface, allowing them to interact with M OBIUS framework components, not formalism components. This permits novel combinations of modeling techniques. The AFI uses abstract classes to implement the framework components. The most basic model in the M OBIUS framework is an atomic model, and is made up of state variables that hold information about the state of a model and actions that are used for changing model state. Stochastic activity networks (SANs) and the stochastic process algebra PEPA are example atomic models that have been successfully implemented in the M OBIUS tool.

The Mobius framework is an environment for supporting multiple modeling formalisms and solution techniques. Models expressed in formalisms that are compatible with the framework are translated into equivalent models using Mobius framework components. This translation preserves the structure of the models, allowing efficient solutions. The framework is implemented in the tool by a well-defined abstract functional interface. Models and solution techniques interact with one another through the use of the standard interface, allowing them to interact with Mobius framework components, not formalism components. This permits novel combinations of modeling techniques, and will be a catalyst for new research in modeling techniques. This paper describes our approach, focusing on the "atomic model". We describe the formal description of the Mobius components as well as their implementations in our software tool.