Categorification of the Müller-Wichards System Performance Estimation Model: Model Symmetries, Invariants, and Closed Forms

In the late 1980s, D. Müller-Wichards proposed a concise novel approach for estimating the total performance of computer-based (but machine independent) applications by algebraically combining the known performance estimates of the individual arithmetic, data movement, and delay elements that comprise the applications in a manner that also accounts for various degrees of parallelism that can occur during processing [1]. The essence of the mathematical framework upon which the Müller-Wichards model (MW) is based is abstracted by the expression $\phi :H\to P$, where $H$ is a monoid (i.e., a semigroup with identity) representation of the application, $P$ is the Müller-Wichards performance algebra (also a monoid), and $\phi$ is a monoid homomorphism. The image $\phi \left(h\right)$ in $P$ of a single application element $h$ in $H$ provides a numerical performance measure for $h$. The total numerical performance estimate for the application results naturally from the associative binary operations in $H$ and $P$ and the homomorphism property of $\phi$, which algebraically combines the performance estimates for each application element in $H$.

Every area of mathematics (e.g., group theory, topology) is described by numerous definitions, theorems, and constructions. However, many common mathematical concepts occur naturally with only slight variation in the various areas of mathematics. Category theory is that branch of mathematics which identifies and studies these common concepts and provides formal mechanisms for mapping them from one area of mathematics to another. More specifically, a category (e.g., the category of sets) consists of a class of objects (e.g., sets), morphisms between objects (e.g., maps between sets), an identity morphism for each object (e.g., the set identity map), and a rule for associatively composing morphisms (e.g., composition of maps). Functors provide formal maps between categories (e.g., from the category of groups to the category of sets) by associating objects and morphisms in different categories subject to the constraints that morphism composition and object identities are preserved.

Because of its generality category, theory has found application in recent years in such diverse areas as physics (e.g., [2,3,4,5]), design specification (e.g., [6,7]), data fusion (e.g., [8]), computer science (e.g., [9]), computer security (e.g., [10,11]), systems engineering (e.g., [12]), manufacturing (e.g., [13]), theoretical biology (e.g., [14,15,16]), network theory (e.g., [17]), multi-agent systems models (e.g., [18]), concurrent system design verification (e.g., [19]), emergence (e.g., [20]), and artificial general intelligence (e.g., [21]). Motivated by category theory’s mathematical precision and expressive power, this paper introduces a new category theoretic application useful for numerical systems engineering modelling and analysis via a very simple straightforward categorification of MW for the case that the application monoid $H$ is a free monoid generated by a finite set of basis processes, i.e., $H$ is the set of all finite sequences of basis processes, including the empty sequence-where each sequence represents a system and each basis process corresponds to either an arithmetic process, a data movement process, or a delay process-and catenation of systems serves as the associative binary operation. The categorified MW-denoted by CMW-is comprised of three components: a single object category of systems that is specified by $H$ and has elements of $H$ as its set of morphisms; a single object performance category that is specified by $P$ and has the elements of $P$ as its set of morphisms; and a performance functor specified by $\phi$ with the category of systems as its domain and the performance category as its codomain.

CMW is effectively numerically equivalent to MW with the added benefit that the formalism introduced by categorification provides a precise vocabulary useful for identifying and discussing certain fundamental properties of both the model and the systems modelled by it. In particular, the CMW fundamental symmetry group is introduced and the category theoretic formalism is used to facilitate the identification of associated symmetry invariants found in the model. In addition, the formalism provides a natural approach to system factorization-i.e., dividing a system into subsystems in a manner that maintains its integrity-i.e., preserves the performance of the undivided system.

As indicated above, the objective of this paper is to provide a categorified version of the MW model and exploit the associated category theoretic vocabulary to provide additional insights into properties of the MW model, as well as the systems modelled by it. In order to make this paper reasonably self-contained, relevant definitions, terminology, and preliminary lemmas are summarized in the next section (for additional depth and clarification the reader is invited to consult such references as [22,23,24]). The remainder of this paper is organized as follows: The Müller-Wichards performance categories are defined, and their category theoretic properties discussed in Section 3. The category of systems and the Müller-Wichards performance functors are introduced in Section 4. The CMW fundamental symmetry group is defined and its associated model invariants are identified in Section 5. System factorization and a “product of categories” performance model are discussed in Section 6. Closed form models are developed in Section 7 and several aspects of closed form models are studied statistically in Section 8. Special case closed form models are developed in Section 9. These special case closed form models are applied in Section 10 to abstractly demonstrate the effect of parallelization on system processing time vs. loading and to obtain a stationary action principle for system performance. Concluding remarks comprise the final section of this paper. To avoid disrupting the flow of the text, proofs for all theorems (including those for the special case closed form models) are consigned to Appendix A.

As mentioned in the introduction, in 1988 Dieter Müller-Wichards posited a (computing) machine independent “performance algebra” designed to estimate the total performance of a specific implementation of an application on a machine using the (known) performance characteristics of its individual building blocks. This approach enabled trade-off studies and analyses of applications using its various decompositions and implementations [1]. As indicated above, similar studies and analyses can be performed using CMW to estimate the numerical performance of any system that can be represented as sequences of arithmetic, data movement, and delay processes.

The Müller-Wichards performance algebra consists of a set whose elements are ordered in triples along with an associative binary operation, which defines how the elements of the set are to be multiplied. These elements are partitioned into three distinct subsets depending upon whether they are arithmetic, data movement, or delay elements. The first and second entries in each triple correspond to a performance value (e.g., a processing or data movement rate) and a weight value (e.g., the number of operations to be performed or the amount of data to be moved), respectively (delay elements are a special case—see below). The third entry is either a $0$-which defines the element as a data movement or delay element-or a $1$-which defines the element as an arithmetic element. Multiplication of an arithmetic element by any element produces another arithmetic element, whereas the product of a data movement element with a data movement element or a delay element is a data movement element. The set of delay elements is closed under this multiplication.

Multiplication is defined in terms of a positive real valued parameter $q$, which provides a family of (“skewed” time) results that interpolate between completely sequential and completely parallel execution of the associated application. The value of this parameter can be selected to account for execution time “speedup” or for degrees of machine and application parallelism.

The sets that define the Müller-Wichards performance algebra are: where $i=\sqrt{-1}$, and

Each element in $C,D,$ and $V$ is a triple $g=\left(r,w,u\right)$, where $r$ is a performance value, $w$ is a weight value, and $u\in \left\{0,1\right\}$ determines the element type (i.e., $C$, $D$, or $V$).

Let $1\le q\le \infty ,$ and define the operation ${\otimes }^q$ as follows:

The elements $g_1,g_2$ are comparable if $g_1,g_2\in C$ or $g_1,g_2\in D$ or $g_1,g_2\in V$. If $g_1,g_2\in \wp$, then $g_1\le g_2$ when $g_1,g_2$ are comparable and either $\frac{\left|w_2\right|}{r_2}<\frac{\left|w_1\right|}{r_1}$ or $\frac{\left|w_2\right|}{r_2}=\frac{\left|w_1\right|}{r_1}$ and $r_2\ge r_1$.

Since $\left(\wp ,{\otimes }^q\right)$ is the monoid $M_q$, then $\left(\wp ,{\otimes }^q\right)$ specifies a category according to the prescription given by the next theorem.

This leads to the following result:

Note that although $Mo{r}_{{\mathit{\wp }}_{\mathit{q}}^{\mathit{X}}}\left(M_q^X,M_q^X\right)\mathit{\subset }\mathit{M}\mathit{o}{r}_{{\wp }_q}\left(M_q,M_q\right)$, ${\mathit{\wp }}_{\mathit{q}}^{\mathit{X}}$ is not a subcategory of ${\mathit{\wp }}_{\mathit{q}}$ because $M_q^X\ne M_q$.

The following result is included for completeness and is a category theoretic statement of the fact that multiplication in the performance algebra is biased towards arithmetic elements, i.e., the product of any element in set $\wp \equiv C{\displaystyle \cup }D{\displaystyle \cup }V$ with an element in set $C$ is an element in $C$.

In this section, the category of systems is obtained from the free monoid ${ℐ}_A$ generated by a finite set $A$ of basis processes. Although this approach is similar to that employed in [1] to define $H$, for simplicity the catenation operation in ${ℐ}_A$ is used here instead of the two operations $\otimes$ and $\oplus$ used in $H$ to distinguish between portions of an application that have sequential and parallel implementations. A product of categories construction will be introduced for this purpose in Section 6.

Recall from Section 1 that ${ℐ}_A$ consists of all finite sequences of basis processes of $A \mathrm{called}\mathrm{s}ystems.$ The catenation of systems $u,v\in {ℐ}_A$ is the system $w=uv\in {ℐ}_A$ and $u$ and $v$ are subsystems of $w$. The empty system $\epsilon \in {ℐ}_A$ is the system with no basis processes and serves as the identity element for ${ℐ}_A$ with $\epsilon u=u\epsilon =u$.

The category of systems ${\mathit{\Im }}_{\mathit{A}}$ associated with a basis process set $A$ is obtained from ${ℐ}_A$, as prescribed in the following theorem.

Thus, a morphism in ${\mathit{\Im }}_{\mathit{A}}$ is a system and composition of morphisms in ${\mathit{\Im }}_{\mathit{A}}$ is catenation of systems.

Any functor from ${\mathit{\Im }}_{\mathit{A}}$ into ${\mathit{\wp }}_{\mathit{q}}$ or ${\mathit{\wp }}_{\mathit{q}}^{\mathit{X}}, X\in \left\{C,D,CD,V\right\},$ is referred to here as a Müller-Wichards performance functor for ${\mathit{\Im }}_{\mathit{A}}$ and the performance for any system in ${\mathit{\Im }}_{\mathit{A}}$ is its image under a Müller-Wichards performance functor in ${\mathit{\wp }}_{\mathit{q}}$ or ${\mathit{\wp }}_{\mathit{q}}^{\mathit{X}}, X\in \left\{C,D,CD,V\right\}$. These functors are defined by unique extensions of gauge maps from the set of basis processes into the associated Müller-Wichards performance monoids as described by the following theorem (here “gauge” emphasizes the fact that these maps set the performance gauge for each basis process).

Based upon the discussion above, it is clear that CMW can be abstracted by the functor expressions $F_{{\phi }_0}:{\mathit{\Im }}_{\mathit{A}}\to {\mathit{\wp }}_{\mathit{q}}$ and $F_{{\phi }_0}^X:{\mathit{\Im }}_{\mathit{A}}\to {\mathit{\wp }}_{\mathit{q}}^{\mathit{X}}, X\in \left\{C,D,CD,V\right\}$. In this section, the CMW fundamental symmetry group is introduced and associated model invariants (which at an abstract level can be viewed as invariants of the modelled system) are identified. Recall that, in general, a symmetry associated with a “situation” is related to an “immunity to change” for some aspect of the “situation”. In order for a “situation” to have a symmetry: (i) the aspect of the “situation” remains unchanged or invariant, when a change or symmetry transformation acts upon the “situation”; and (ii) it must be possible to perform the change, although the change does not actually have to be performed [26]. Here, symmetry and symmetry transformation are used interchangeably.

An automorphism of ${\mathit{\Im }}_{\mathit{A}}$ is a bijection $\alpha :Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)\to Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)$, which preserves the catenation operation in ${ℐ}_A$. Since $Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)$ remains unchanged under $\alpha$ and it is possible-but not necessary-to apply $\alpha$, then items (i) and (ii) above are satisfied and $\alpha$ is a ${\mathit{\Im }}_{\mathit{A}}$ symmetry. The set of all such symmetries under the operation composition of bijections forms the automorphism group $Aut({\mathit{\Im }}_{\mathit{A}}$). This group is the CMW fundamental symmetry group.

The following corollary is obvious and is stated without proof.

A CMW invariant is a CMW property that remains unchanged after every symmetry in the CMW fundamental symmetry group has been applied to $Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)$.

Recall from Section 2 that a morphism $h$ is factorizable if $h=f\circ g$, where $f$ is a monic morphism and $g$ is an epic morphism. In the category of systems, this means that when a system $w$ is factorizable as $w=uv$, then $w$ can be divided into the two subsystems $u$ and $v$ without affecting the order and content of the base processes in $w$. The integrity of a factorization is maintained if the performance of $w$ is identical to that of $uv$.

A commutative square in ${\mathit{\Im }}_{\mathit{A}}$ corresponds to an equation $uv=wz$, where $u,v,w,z\in Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)$.

Results similar to Corollary 3 also apply for $F_{{\phi }_0}^X,$ $X\in \left\{C,D,CD,V\right\}$.

Additional modelling flexibility can be obtained using products of categories when a system is comprised of subsystems that have different sequential and/or parallel characteristics. Here, two basis sets $A$ and $B$ of processes and two morphism compositions ${\otimes }^q$ and ${\otimes }^p$ form the product category of systems ${\mathit{\Im }}_{\mathit{A}\mathit{B}}={\mathit{\Im }}_{\mathit{A}}\times {\mathit{\Im }}_{\mathit{B}}$ and the associated Müller-Wichards product performance category ${\mathit{\wp }}_{\mathit{q}\mathit{p}}={\mathit{\wp }}_{\mathit{q}}\times {\mathit{\wp }}_{\mathit{p}}$, respectively. For the product category ${\mathit{\Im }}_{\mathit{A}\mathit{B}}$ the single object is the pair $Ob{j}_{{\mathit{\Im }}_{\mathit{A}\mathit{B}}}=Ob{j}_{{\mathit{\Im }}_{\mathit{A}}}\times Ob{j}_{{\mathit{\Im }}_{\mathit{B}}}=\left\{\left({ℱ}_A,{ℱ}_B\right)\right\}\equiv \left\{{ℱ}_{AB}\right\},$ the set of morphisms are ordered pairs $Mo{r}_{{\mathit{\Im }}_{\mathit{A}\mathit{B}}}\left({ℱ}_{AB},{ℱ}_{AB}\right)=Mo{r}_{{\mathit{\Im }}_{\mathit{A}}}\left({ℱ}_A,{ℱ}_A\right)\times Mo{r}_{{\mathit{\Im }}_{\mathit{B}}}\left({ℱ}_B,{ℱ}_B\right)$ such that for $\left(f_A,f_B\right)\in Mo{r}_{{\mathit{\Im }}_{\mathit{A}\mathit{B}}}\left({ℱ}_{AB},{ℱ}_{AB}\right)$, $f_A:{ℱ}_A\to {ℱ}_A$ and $f_B: {ℱ}_B\to {ℱ}_B$ with composition performed component wise. Similarly, for the product category ${\mathit{\wp }}_{\mathit{q}\mathit{p}}$ the object is the pair $Ob{j}_{{\mathit{\wp }}_{\mathit{q}\mathit{p}}}=Ob{j}_{{\mathit{\wp }}_{\mathit{q}}}\times Ob{j}_{{\mathit{\wp }}_{\mathit{p}}}=\left\{\left(M_q,M_p\right)\right\}\equiv \left\{M_{qp}\right\}$, the set of morphisms are ordered pairs $Mo{r}_{{\mathit{\wp }}_{\mathit{q}\mathit{p}}}\left(M_{qp},M_{qp}\right)=Mo{r}_{{\mathit{\wp }}_{\mathit{q}}}\left(M_q,M_q\right)\times Mo{r}_{{\mathit{\wp }}_{\mathit{p}}}\left(M_p,M_p\right)$ such that for $g_{qp}\equiv \left(g_q,g_p\right)\in Mo{r}_{{\mathit{\wp }}_{\mathit{q}\mathit{p}}}\left(M_{qp},M_{qp}\right)$, and $g_p: M_p\to M_p$ with composition performed component wise. It is easily verified that ${\mathit{\Im }}_{\mathit{A}\mathit{B}}$ and ${\mathit{\wp }}_{\mathit{q}\mathit{p}}$ are categories where $1_{{ℱ}_{AB}}=\left(\epsilon ,\epsilon \right)$ and $1_{M_{qp}}=\left(\left(\infty ,i,0\right),\left(\infty ,i,0\right)\right)$ are the object identities.

Now use the gauge maps ${\phi }_0:A\to \left(\wp ,{\otimes }^q\right)$ and ${\theta }_0:B\to \left(\wp ,{\otimes }^p\right)$ to define $F_{{\phi }_0,{\theta }_0}:{\mathit{\Im }}_{\mathit{A}\mathit{B}}\to {\mathit{\wp }}_{\mathit{q}\mathit{p}}$ as $F_{{\phi }_0,{\theta }_0}\equiv F_{{\phi }_0}\times F_{{\theta }_0}=\left(F_{{\phi }_0},F_{{\theta }_0}\right)$ such that $F_{{\phi }_0,{\theta }_0}{ℱ}_{AB}=\left(F_{{\phi }_0}{ℱ}_A,F_{{\theta }_0}{ℱ}_B\right)=\left(M_q,M_p\right)=M_{qp}$ and for $f\equiv \left(f_A,f_B\right)\in Mo{r}_{{\mathit{\Im }}_{\mathit{A}\mathit{B}}}\left({ℱ}_{AB},{ℱ}_{AB}\right)$, $F_{{\phi }_0,{\theta }_0}f=\left(F_{{\phi }_0}{f}_A,F_{{\theta }_0}{f}_B\right)=\left(g_q,g_p\right)=g_{qp}$. It is readily seen that $F_{{\phi }_0,{\theta }_0}$ is a functor because $F_{{\phi }_0,{\theta }_0}{1}_{{ℱ}_{AB}}=\left(F_{{\phi }_0}\epsilon ,F_{{\theta }_0}\epsilon \right)=\left(\left(\infty ,i,0\right),\left(\infty ,i,0\right)\right)=1_{M_{qp}}$ and for $h,k\equiv \left(h_A,h_B\right),\left(k_A,k_B\right)\in Mo{r}_{{\mathit{\Im }}_{\mathit{A}\mathit{B}}}\left({ℱ}_{AB},{ℱ}_{AB}\right)$, if, then $F_{{\phi }_0,{\theta }_0}f\circ h=F_{{\phi }_0,{\theta }_0}\left(f_A\circ h_A,f_B\circ h_B\right)=\left(F_{{\phi }_0}{f}_A\circ h_A,F_{{\theta }_0}{f}_B\circ h_B\right)=\left(F_{{\phi }_0}{k}_A,F_{{\theta }_0}{k}_B\right)=F_{{\phi }_0,{\theta }_0}k$.

Thus:

Of course, a similar construction can be made using products of a finite number of categories of systems and Müller-Wichards performance categories.

Thus, generally distinct performance triples $g_q\equiv \left(r_q,w_q,u_q\right)$ and $g_p\equiv \left(r_p,w_p,u_p\right)$ are obtained, which yield separate performance estimates for systems comprised of $A$ basis processes and for systems comprised of $B$ basis processes, respectively. Obviously, unless $q=p$, $g_q$ and $g_p$ cannot be properly combined algebraically to obtain a single performance estimate for a process comprised of both $A$ and $B$ basis processes. However, an inequality can be established by letting $g_1=g_q, g_2=\left(\infty ,i,0\right)=g_3,$ and $g_4=g_p$ in Lemma 2.6 in [1]. These yields $g_q{\otimes }^p{g}_p\ge g_q{\otimes }^q{g}_p$ when $1\le q\le p\le \infty$. An alternative approach is to estimate the combined processing time for systems composed of $A$ processes and for systems composed of $B$ processes from $g_q$ and $g_p$ using $t_{AB}=t_A+t_B$, where $t_A=\frac{\left|w_q\right|}{r_q}$ and $t_B=\frac{\left|w_p\right|}{r_p}$.

In this section, the above theory is used to develop general closed form system performance estimation models where a system’s performance $r$ and weight $w$ are explicit functions of the performances and weights of the processes that comprise the system. The next theorem provides models for systems comprised entirely of a finite number of arithmetic processes or data movement processes. In what follows, let $N=\left\{1,2,\cdots ,n\right\}$.

Now consider systems comprised entirely of a finite number of delay processes.

The last two theorems can be used to construct closed form models for systems comprised of finite numbers of arithmetic, data movement, and delay processes.

Since system performance studies are often stochastic in nature, it is instructive to examine the statistical characteristics of the system performance variable $r$ for several cases using the closed form models of Theorem 17 for arithmetic and data movement elements.

Here, Theorems 17–19 are used to produce several closed form models when the performance values and the weight values are assumed to be equal for all processes in a system. Such processes are equal processes and the associated system models are special case closed form models (SCCFMs).

Since the next model is also a direct consequence of Theorem 17 and its proof follows that of the previous model, it is stated without proof.

Note that: (i) when $q=1$, the processing is sequential and as required, the time $t_1^X, X\in \left\{C,D,V\right\},$ for the systems to complete their processing is the sum of the $n$ individual times required to complete each process in the system; (ii) when $1<q<\infty$, the processing time is “skewed” or “compressed” and $t_q^X<t_1^X$.

The time required for this system to complete its processing is:

Again, note that when $q=1$, $t_1^{CDV}$ is the sum of the system delays, the time required for the system to complete processing its arithmetic operations, and the time required for the system to complete its data movement operations.

Special case closed form models are useful for understanding and describing fundamental properties and dynamics of CMW system performance models. The following subsections provide several examples of this.