Tag: monoids

Categories
Uncategorized

simple lemma about pipelines

The connection between group structure and pipeline design seems like it merits a lot more attention than it gets. It’s not too hard to show that in a pipeline like the one to the right, the induced monoid of M1 must be a homomorphic image of the composite state machine. This immediately brings in the limiting factors of simple groups.

KR theory is too vague though. For example, I’d like to know something about the relationship of M and M’ in the case that the induced monoids are isomorphic. They definitely do not have to be the same, but seems like they should be similar enough so that changing the output map would equalize.

Categories
Uncategorized

sequential and combinational state machines

There’s a correspondence between the notions of “combinational” and “sequential” in digital circuit engineering and some structure in state machines (and therefore monoids)  that seems interesting.

In digital logic, a “combinational” circuit like a logic gate has can be associated with a time T so that the output depends only on input signals applied over the last T time units. If the propagation delay is T, then signals applied T+n time units ago are irrelevant to current state.  For example, an AND gate with propagation delay T has output 1 if all inputs have been set HIGH over the last T time units. For a sequential circuit, like a latch, there is no magic time T. Suppose we set the stored value in the  latch at time T1 and then signal it to hold the value. No matter how long the latch is held, we have to go back to absolute time T1 to find out what is in the latch. It’s worth noting however, that it’s often very useful to make a sequential circuit have a reset mode where it behaves like a combinatorial circuit. That is, we want to be able to say: no matter what previous signals have done to a memory device, some sequence of signals will clear it and, for example,  put the number 3 in it. More on this below.

Take a Moore machine M and write State(M,w) for the state reached by following input string “w” from the initial state. I’m limiting us to complete Moore machines where State(M,w) must be defined for every w.  Say M is combinational if there is some T so that if w=uz and length(z)>T then State(M,w)= State(M,z) . So the idea is that there is a T so that the last T inputs determine state for M. Call T the “depth” of M. As an example, suppose M represents a memory location and the inputs are just data values to store. Then we only need the last input, T=1.  If M is an AND gate with two pins and a delay of 2, then we can think of inputs as numbers 0,1,2,3 representing their 2 bit encodings: 0 for 00, 1 for 01, 2 for 10 and 3 for 11.  States can be pairs [x1,x2] representing the last two inputs so that if the state is [a,b] and input “c” is received, the new state is [c,b].  The state is actually a shift register. Suppose that the states are all pairs [x1,x2] where x1 and x2 are in the set {-1,0,1,2,3} with “-1” representing  an unknown signal. Then [3,3]  has output 1, [x1,x2] where both x1 and x2 are greater than -1 and less than 3 outputs 0 and the others have undefined output. The initial state is [-1,-1]. Obviously this machine is combinational with depth T=2. The intuition here is that combinatorial state machines will always “swim” to a fixed state given a fixed sequence of inputs of sufficient length. Obviously, this is a useful property of a device and even for sequential devices we are going to want some single or sequence of “reset” operations that, no matter what the current state, will force a reset to a known state. That is, for our latch, we’d want to force it to an assigned latched value, no matter what, if anything, it had previously latched. So properly designed sequential circuits are going to look like some combination of combinatorial and sequential circuit.

Now consider products of state machines. The method I’ve been using for representing state machines as maps f:InputSequences ->Outputs is convenient for products. If f represents a state machine M, then f(w) = Output(State(M,w)). If f represents a combinational state machine of depth T then f(wuz)= f(uz) whenever length(u)>T because State(M,wu)=State(M,u) so State(M,wuz)=State(M,uz) so the outputs must be the same.  Say F(w) = (g1(w1) …, gn(wn)) is a product under connection function Phi and map w |-> w1 … ,wn if when w=empty then wi = empty for all i and if when w maps to wi then wa maps to wi.Phi(a,i,F(w)) with ‘.’ representing string concatenation. Say that F is a cascade product if and only if  Phi(a,i,(x1 … xn)) depends only on xj for j < i. That is, in a cascade product, information only flows from lower numbered factors to higher numbered ones: there is no feedback in a cascade product. If g1 …,gn are combinatorial AND Phi(a,i,(x1 …,xn)) !=empty for any combination of parameters, and F is a cascade product, then F must be combinatorial. For proof, suppose Ti is the depth of each component gi and suppose w=uv where length(v)> T1. Then w1= u1.v1 where length(v1)> T1 so g1(v1)=g1(w1) and more than that g1(w1.z)=g1(v1.z) for all z.  That means Phi(a,i,F(wa))=Phi(a,F(va)) by the cascade property. And so on – eventually we see that the depth of F is the sum of the depths of the factors! For intuition, first we need enough inputs to steer factor 1 to a known state, then factor 2 and so on.

Given a state machine M with states S, we can associate a map from S to S with every string of inputs w so that F(M,w)(s)=s’ if and only if w leads from s to s’. This set of maps forms a monoid under ordinary function compositions  and since F(M,w)(F(z)(s))= F(M,wz)(s) then F(M,w)+F(M,z)= F(M,wz) where + is the monoid operation and not anything necessarily related to arithmetic. The empty string produces the monoid identity F(M,empty)(s)=s.  Look at the monoid structure of combinatorial state machines and note that unless the monoid is trivial, then  F(M,w)=F(M,empty) only if w=empty – there are no other identities.

The proof is easy. Suppose M is combinatorial  with depth T, the monoid is not trivial so that for some v we have F(M,v) != F(M,empty)and suppose F(M,z)=F(M,empty).  Then if z is not empty let Z consist of a string of concatenated z’s that is longer than T  so Z=zzzzzz …. stretched out to a length greater than T. By the combinatorial property, for any u, F(M,uZ)(s)=F(M,Z)(s) but because F(M,z)=F(M,empty) we also know F(M,uZ)(s)=s so F(M,w)(s)=s for all w and s which implies the monoid is trivial after all. It’s also worth pointing out that the combinatorial monoids seem to be a proper subset of the aperiodic monoids ( http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf ). Consider the state machine with states {0,1,2} and inputs {a,b} so that, treating the inputs at maps from state to state, a(0)=1 and b(0)=2 for any non-zero state we have x(s)=s. The monoid is clearly aperiodic since a2=a 3 , a2(0)=1 and a2(s!=0)=s. But the state machine is not combinatorial.

Well, more later, but that’s what I have semi-clearly explicated for now. I’ll leave you with this photograph of Camille Jordan who lived in an unenlightened era that did not make clear demarcations between mathematics and mere engineering.

Categories
algebra

Data structures and algebra

[Edited 9/10] There’s an easy connection between data structures and basic abstract algebra that may or may not mean anything, but keeps getting rediscovered. I’ve never seen it clearly explained (anyone with a reference or who notices an error in my rusty algebra- please send me a note! A discrete note would be nice -) ).

What keeps on getting rediscovered is that objects with invertible and commutative methods would make things very convenient especially for transactions and for concurrent access. What I have not seen explained is that this discovery reflects the distinction between groups and monoids.

A monoid is one of the simplest algebraic structures and is usually given as a set M of elements and and a binary operation \(\circ\) on elements of M with the following properties:

  • Closure: for every a and b in M, \(a \circ b\in M \).
  • Associative:    \(a \circ  \) \(( b \circ c ) \) = \((a \circ b) \circ c \) for every a, b, and c in M
  • Identity: M contains an element I so that for every \( a \in M, I \circ a = a \circ I =a \).

That’s it. A pair \((M,\circ)\) and three conditions: closure, associativity and identity. The natural numbers 0,1,2,… form a monoid with ordinary integer addition as the operation and 0 as the identity. The positive numbers form a monoid with 1 as the identity and multiplication as the operation. More intriguingly for our purposes, the methods of an abstract data type or object generate a monoid.

A monoid \( (M, \circ)\) is “generated” from a set X if and only if X is a subset of M and every element of M can be constructed from elements of X using the operation. For example, the monoid of non-negative integers with addition as the operation can be generated from \(\{0,1\}\) since \(2= 1+1, 3 = (1+1)+1\) and so on. One really simple type of monoid is the set \(E^*\) of all finite strings that can be generated from an alphabet with string concatenation as the operator.

We can use the methods of an object as the generators of a monoid as follows. Let’s define an object by a set V of possible values and a set F of methods that can act on the object. A method is really just a function from V to V so that if the object has value v and we apply method f the object value becomes f(v). The binary associative operation of “function composition” can be used to construct “programs” from methods: \(f (gh))(v) = f(g(h(v)))\). The monoid generated by the methods, then, is the set of programs that can be constructed using function composition on the methods. All we have to do further is insist that there is a null method \(Null(v)= v\) is in F.

For example, if our data structure is a stack and our methods are \(push_v\) for every v in some set of values V, plus pop, add (pop the top two values, add and push the result), sub, dup, swap, and \(null\), we can build a Forth Monoid.

If a is an element of a monoid and there is a second element b so that \(a \circ b = I\)  then b is called the “inverse” of a. If there is an inverse for every element of the monoid, then the monoid is called a “group”. (Note that in a group if b is the inverse of a, then a is the inverse of b because of associativity. If the group operation commutes, the group is called Abelian or commutative.

Most monoids are not groups. For example, our Forth Monoid has an inverse for “dup” (“pop” ) but pop does not have an inverse for a very interesting reason: pop loses information. Add has no inverse for the same reason: if the stack is (100,200) and an add method produces (300), then there is no operation that will deduce magically that 100 and 200 were on the stack before and not (0,300) or (1,299) or …  Monoids that are not groups lose information when they compute programs. If an object is associated with a group, then no matter what the starting value of the object, if we know the program that was applied to the object, we can produce (in theory) an anti-program that returns us to the initial state. An example of an object that generates a group is an incrementer with the single method “add1” with values over the set 0 – (232 -1) The inverse of add1 is sub1 which can be generated by 232 add1’s (note that  the words “efficient” or “practical” did not appear anywhere above).

It has been noticed more than once that data structures whose monoids are groups would be easier to parallelize or to use for transactions. For example, if programs can be inverted: so that for every program p there is a -p with -pp = I then we can unroll back to earlier states. That is, if we apply f,g,h to the data structure, and then realize that the transaction cannot be completed, we know that \(-h(-g(-f(f(g(h(x)))))) = x\). We do not have to know what “x” was to undo the transactions. If the programs “commute”, life is even easier, since undoing a single method application can be done at any time, without undoing other method applications. With a little thought you can see that a commutative group data structure is convenient for parallel computation because the order of operations doesn’t matter (less synchronization required) and because every operation is reversible. So if Task T starts modifying the data structure and more important task K interrupts, T’s partially completed changes to the data structure can be rolled back and K can do what it needs.

I’m not completely convinced that stumbling into group theory tells us anything useful about data structures except that computer science is hard and is mostly concerned with horribly irregular structures that do not possess convenient properties. But groups and monoids keep popping up in computer science, even though theoretical CS people seem to not be interested anymore. Famously, state machines determine monoids (or semi-groups) and there is a body of mathematics called Krohn-Rhodes theory which is concerned with factoring monoids into cascades of groups and residual monoids that correspond with splitting state machines into pipelines that have no feedback. Also there is a nice relationship between logging and group structure: Most data structures cannot be practically converted into group like structures even though every monoid can be made into a group by adding a log.

Suppose we make our Forth object have values (data-stack,log-stack) where the log-stack is essentially a stack of data removed from the stack so that “pop” removes the top element of the stack and pushes it onto the log stack – then “invert-pop” can pop the log-stack and push the value onto the data stack. I wonder if “bounded invertibility” would be an interesting property. The interesting Forth objects have a bounded stack anyways. Suppose we add a smaller log-stack so we can invert some programs: suppose the methods are invertible and programs constructed by composing at most K methods are invertible.

Anyways, there is something worth digging out in all this: think of filesystems designed to be K-deep group-like.

(I was inspired or provoked to produce this note after attending a talk by Maurice Herlihy at UT. I can’t say I understood much of Professor Herlihy’s talk (my fault, not his) but he was discussing the utility of converting data structure monoids to groups without mentioning either groups or monoids. I also found out that distributed shared memory is still around- how depressing.)