The Klein 4-group

[Anko]

Hello.
I'm going over some old uni notes, and I'm hoping to learn a bit more about categories and things like fibrations.
But in 3rd year, we looked at the Klein 4-group. I know of two examples, one where I can have an additive V₄ acting on pairs of two-way crossbar switches, in what I suppose is the Benes construction or switching net.

The other is when it acts on a 4-tuple of vertices, in the rotation subgroup of D₄ if I give each vertex of the square an index from {00, 01, 10, 11} then I add 1 to the appropriate row or column index, four at a time. So V₄ is in both places as a free additive group, which I need to restrict?

The thing I'm getting at I think is, what does any restriction on V₄ then have to do with an inductive kind of algorithm, particularly in the Benes construction, where the other half of the exercise is to route inputs to outputs, without blocking. Thus a switching algorithm is a requirement.

 

[WWGD]

Maybe @fresh_42 can help here?

 

[martinbn]

I think you need to give more context. For example you could write the full text of the exercise you have looked at, and anything relevant to it.

 

[Anko]

The exercise didn't have much in the way of text. It was a course by a lecturer called Bob Hoskins (I may have misspelt that, sorry Bob), at year 4 and was about parallel processing models like PRAM etc. We were handed a diagram of a 16-input, 16-output Benes network and asked to write some program that could model it and investigate the problems with routing requests in parallel.

I realized fairly quickly that the worst case is when 16 requests arrive and want the same output. Then you are blocked and queing requests. That means perhaps you have to order them, or perhaps randomly connect them, or maybe there is a priority to deal with. Even if each request is for a different output, then switching everything the right way, in parallel, is NP-hard, I think. I could be wrong about that, I didn't get to find out.

So now I would like to look at this somewhat dated problem, from the point of view of a group algebra,
and see if there is a program algebra that guarantees an algorithm will work correctly, and if it can do this in parallel (I think there are too many restrictions, and that's the first thing to make a list of)

 

[Office_Shredder]

.I realized fairly quickly that the worst case is when 16 requests arrive and want the same output. Then you are blocked and queing requests. That means perhaps you have to order them, or perhaps randomly connect them, or maybe there is a priority to deal with. Even if each request is for a different output, then switching everything the right way, in parallel, is NP-hard, I think. I could be wrong about that, I didn't get to find out.

I just read what s Bene Network is for this thread, and I think in the case that your routing is a permutation from inputs to output it is actually very easy to pick a routing which is totally parallel. All it requires is 2 coloring a bunch of graphs that are guaranteed to be 2 colorable, which seems simple to me.

 

[mathwonk]

forgive me, but now I may have a clue why I seem to be on the wrong track here:
https://www.cnn.com/2014/04/30/showbiz/obit-bob-hoskins/index.html

 

[WWGD]

forgive me, but now I may have a clue why I seem to be on the wrong track here:
https://www.cnn.com/2014/04/30/showbiz/obit-bob-hoskins/index.html

Well, he died 10 years back, almost, in 2014.
Edit: Never mind.

 

[Anko]

I just read what s Bene Network is for this thread, and I think in the case that your routing is a permutation from inputs to output it is actually very easy to pick a routing which is totally parallel. All it requires is 2 coloring a bunch of graphs that are guaranteed to be 2 colorable, which seems simple to me.

But it isn't simple. Say you have 16 inputs and a request arrives at each one. In packet switching networks all packets have an address. So now you have to route 16 requests to 16 outputs and you can't assume they want a different output. Even if they did, can you route all 16 simultaneously?

 

[Office_Shredder]

But it isn't simple. Say you have 16 inputs and a request arrives at each one. In packet switching networks all packets have an address. So now you have to route 16 requests to 16 outputs and you can't assume they want a different output. Even if they did, can you route all 16 simultaneously?

If they all want a different output, you can route them all simultaneously. The algorithm is described here

https://eng.libretexts.org/Bookshel...:_Communication_Networks/10.09:_Benes_Network

If some of them want the same output, you could probably tweak this to try to minimize congestion

 

[Anko]

If they all want a different output, you can route them all simultaneously. The algorithm is described here

I don't know about the simultaneous routing though. You still need an algorithm that sequentially determines the graph coloring before the connections are made, which is then possible simultaneously. Is that something that could be done in parallel? It wouldn't be as easy as the sequential approach.

 

[Office_Shredder]

I don't think I fully understand the question.

For example, is it "given a mapping from input to output with no overlap, pick the full route of every packet with an algorithm that is polynomial time in the number of inputs"?. Or something else