How to observer the Deadlock scenario....

F. A. Faisal

unread,

May 27, 2015, 3:03:37 AM5/27/15

to topaz-...@googlegroups.com

Hi,

I like to find the deadlock situation with minimum number of VCs for 2D-MESH network. In the below router configuration for 2D-MESH network, I have use 5 Vnets. As the minimum required number of VCs for 2D-MESH network is 1, it should be able to extract any result. But I found that it still unable to produce any result and gives below error. So please let me know why and how I can avoid this scenario.

-------------

</SimpleRouter>

</Router>

-------------

Results:

_________

$ ./TPZSimul -s M44-WH-NOC -c 20000 -l 0.02 -t BIT-REVERSAL -D

Simulating..

File= ../src/TPZInterfaz.cpp

Line= 418

Text= TPZInterfaz: Channel ' 6' not valid5ROUTER(3,0,0)

_________

Thanks in advance...

Pablo Abad

unread,

May 27, 2015, 4:25:36 AM5/27/15

to topaz-...@googlegroups.com

Please, check in the Simula.sgm file that the number of message types is also set to 5. I have the impression that you have a 6 there.

Regards.

--
You received this message because you are subscribed to the Google Groups "topaz-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to topaz-discus...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

F. A. Faisal

unread,

May 28, 2015, 1:00:52 AM5/28/15

to topaz-...@googlegroups.com

Many many thanks for your earliest reply.

And you are right about the Simula.sgm file.

But the main problem is still I am unable to find the deadlock situation. Please consider the below scenario where I put the VCs = 1 in a 2d-torus network and put very high load on the 4x4 Torus network but still it is able to show the results properly!!! (didn't create the abort situation). As I know the minimum required number of VCs for 2D-Torus network is 2. Then VC=1 should generate the deadlocks and also I tried with reduced buffer size but it doesn't have any affect and also with the 3D-torus network. Please let me know your explanations.

Router.sgm

__________

</SimpleRouter>

</Router>

simula.sgm

---------------

</Simulation>

Result:

-----------

$ ./TPZSimul -s T44-CT-NOC -c 20000 -l 0.9 -t BIT-REVERSAL -D

Simulating..

************

******************* NET CONFIGURATION *********************

Network : Torus(4,4,1)

Buffer control : CT

Routing control: TORUS-DOR

Started at : Thu May 28 13:49:58 2015

Ended at : Thu May 28 13:49:58 2015

***********************************************************

Simulation time = 00:00:01 (1 secs)

Memory Footprint = 0 MBytes)

Traffic Pattern = Bit reversal

Seed = 113

Cycles simulated = 20000

Cycles deprecated = 0

Buffers size = 10

Messages length = 1 packet(s)

Packets length = 5 flits

************************ PERFORMANCE ***********************

Supply Thr. Norm = 1.34922 flits/cycle/router

Accept Thr. Norm = 0.286656 f/c/r (m: 0, M:0.7578)

Supply Thr. = 21.5875 f/c

Throughput = 4.5865 f/c (m: 0, M:12.1248)

Average Distance = 2.81598

Messages generated = 86350

Messages received = 18346

Messages to inject = 126

Messages on Escape = 0

Total message latency = 189.217

Network message latency = 52.8451

Buffer message latency = 136.371

Maximum message latency = 1682

Last Message cycle = 20000

***********************************************************

Pablo Abad

unread,

May 28, 2015, 2:55:00 AM5/28/15

to topaz-...@googlegroups.com

If you implement your router with TORUS-DOR routing control, Bubble Flow control is implemented inside the router, avoiding deadlock with a single virtual channel. You have two options, change routing control to MESH-DOR (Despite of the “mesh” in the name, I think it can be employed on a torus topology) or modify TPZSimpleRouterFlowTorus.cpp to eliminate Bubble Flow control (line 331).

Regards.

F. A. Faisal

unread,

May 28, 2015, 3:43:29 AM5/28/15

to topaz-...@googlegroups.com

Thanks for reply.

Actually my goal is to know the minimum number of VCs, which is required to become deadlock free. To Check this I want to enforce the deadlock situation with VC=1, whereas minimum required number of VCs for 2D-Torus is 2. So can you please tell me why I am still obtaining dynamic performance with VC=1 using topaz?

Thanks again...

Pablo Abad

unread,

May 28, 2015, 3:53:09 AM5/28/15

to topaz-...@googlegroups.com

The number of virtual channels required to avoid deadlock depends on the Flow Control employed and the Routing Policy . With Bubble Flow Control and DOR routing, a single virtual channel is enough to avoid deadlock in a Torus. Alternative solutions employ additional virtual channels to break cyclic dependencies or to implement more flexible routing strategies.

You obtain performance in TOPAZ because network is deadlock-free.

F. A. Faisal

unread,

May 28, 2015, 12:05:16 PM5/28/15

to topaz-...@googlegroups.com

Thanks...

As you said earlier, I have tried the below solutions with MESH-DOR and both WH & CT with 1 VC.

But unfortunately it is still producing dynamic performance and not deadlocked for 4x4 Torus network.

Please let me know your suggestion to obtain deadlock situation with 1 VCs in a 4x4 Torus network.

--------------------

......

</Router>

--------------------

........

</Router>

--------------------

Again Many Many Thanks...

Pablo Abad

unread,

May 28, 2015, 12:36:02 PM5/28/15

to topaz-...@googlegroups.com

Try the second solution, modify the file I suggested in my previous mail. Anyway, for both solutions try with a larger network (8*8) and more cycles, deadlock should appear. Try also a non uniform traffic such as bit-reversal...

--

F. A. Faisal

unread,

May 29, 2015, 1:10:12 AM5/29/15

to topaz-...@googlegroups.com

Still I have no good luck yet.

I tried both the solutions and still it is deadlock free. Please find the below changes as you had recommended.

As I learned that DOR is a deadlock free routing with 1 VC, I think we need to try other routing method which can be the only way. Hence please suggest me any more alternatives.

Thanks...

Network.sgm

-----------------

Simulation Condition

---------------------------

./TPZSimul -s T44-CT-NOC -c 100000 -l 0.9 -t BIT-REVERSAL -D

Router.sgm

----------------

CT Flow:

.........

</Router>

and also WH Flow:

........

</Router>

TPZsimple

--------------

if( outputInterfaz(outPort)->isStopActive(virtualChannel) ) {

if( ! m_token ) m_token = inPort;

continue;

}

//if we are changing direction or injecting, bubble must be verified

/*

if( ! m_connections[outPort] && ( ! m_changeDirection[inPort] || bubbleReady(outPort+m_ports*(virtualChannel-1)) ) ) {

// Occupy the port

m_connections[outPort] = inPort;

#ifndef NO_TRAZA

TPZString texto = getComponent().asString() + " SW ARB [GRANT] ";

texto += " From ";

texto += m_routing[inPort]->asString() + " TIME: " + TPZString(getOwnerRouter().getCurrentTime());

texto += TPZString(" inPort: ") + TPZString(inPort) + TPZString(" outPort: ") + TPZString(outPort);

texto += TPZString(" VChannel: ") + TPZString(virtualChannel);

TPZWRITE2LOG(texto);

#endif

} */

// else

{

#ifndef NO_TRAZA

TPZString texto = getComponent().asString() + " SW ARB {REJECT] ";

texto += TP

..........

F. A. Faisal

unread,

Jun 1, 2015, 12:27:32 AM6/1/15

to topaz-...@googlegroups.com

I have another findings-

> If I hide the bubbleReady checking from line 331 of TPZSimpleRouterFlowTorus.cpp, it always shows "nan" in Total message latency for 3D-TOURS network for any number of VCs. But in case of 2D-torus network it could able to show the result as I explained above...

if( ! m_connections[outPort] && ( ! m_changeDirection[inPort] /*|| bubbleReady(outPort+m_ports*(virtualChannel-1))*/ ) )

Pablo Abad

unread,

Jun 1, 2015, 3:28:07 AM6/1/15

to topaz-...@googlegroups.com

You should also comment the m_changeDirection part: if( ! m_connections[outPort] /*&& ( ! m_changeDirection[inPort] || bubbleReady(outPort+m_ports*(virtualChannel-1)) )*/ )

I have made a small experiment to check your issue. After commenting the line as showed above, For a 8x8 torus network I gradually increase the tag "StopInjectionAfterMsg", and simulate until I find a number in which not all the messages are able to reach destination, meaning that I have reached a deadlock situation.

For the following number of messages generated:

And the following execution command (Buffer size moved to 11 flits):

./TPZSimul -s T88-CT-NOC -c 200000 -l 1 -t RANDOM -m 10000

Here are the simulation results:

Simulating..

************

******************* NET CONFIGURATION *********************

Network : Torus(8,8,1)

Buffer control : CT

Routing control: TORUS-DOR

Started at : Mon Jun 1 09:16:22 2015

Ended at : Mon Jun 1 09:16:22 2015

***********************************************************

Simulation time = 00:00:31 (31 secs)

Memory Footprint = 87.6953 MBytes)

Traffic Pattern = Random

Seed = 113

Cycles simulated = 200000

Cycles deprecated = 0

Buffers size = 11

Messages length = 1 packet(s)

Packets length = 5 flits

************************ PERFORMANCE ***********************

Supply Thr. Norm = 0.195312 flits/cycle/router

Accept Thr. Norm = 0.171104 f/c/r (m: 0.08195, M:0.2004)

Supply Thr. = 12.5 f/c

Throughput = 10.9506 f/c (m: 5.2448, M:12.8256)

Average Distance = 4.06248

Messages generated = 500000

Messages received = 438026

Messages to inject = 61910

Messages on Escape = 0

Total message latency = 12350.8

Network message latency = 46.402

Buffer message latency = 12304.4

Maximum message latency = 27232

Last Message cycle = 66291

***********************************************************

**********************************************************

Time f/c/r f/c TotLat NetLat AverDist MaxCons AvgCons

**********************************************************

10000 0.588 37.656 2079.442 48.823 4.061 0 0.00

20000 0.591 37.855 6144.756 49.157 4.074 0 0.00

30000 0.579 37.041 10216.753 48.734 4.055 0 0.00

40000 0.516 33.051 14224.940 45.609 4.057 0 0.00

50000 0.461 29.491 18166.965 43.129 4.054 0 0.00

60000 0.460 29.454 22012.876 43.221 4.071 0 0.00

**********************************************************

Hops Message Count Percent

**********************************************************

0 28115 6.419

1 55512 12.673

2 82939 18.935

3 97886 22.347

4 83320 19.022

5 55378 12.643

6 27904 6.370

7 6972 1.592

As you can observe, even simulating 200,000 cycles the last consumption is at cycle 66,291. Not all the messages have been able to reach destination, because they are permanently blocked (DEADLOCK).

--

F. A. Faisal

unread,

Jun 2, 2015, 12:20:48 AM6/2/15

to topaz-...@googlegroups.com

Dear Pablo,

Thanks a lot for all your effort.

Though in my simulator I can't obtain the same result as you even having the same simulation condition.

But as I run the above simulation, I have found that this network is always in deadlock condition regardless of what is the number of VCs !!!

I tried the simulation with different VCs but the result is the same!!! For your reference I also like to share my simulation condition-

$ ./TPZSimul -s T88-CT-NOC -c 200000 -l 1 -t RANDOM -m 10000

</Simulation>

...........

</Router>

Reply all

Reply to author

Forward