192 - Synchronous Design

[Adrian Kuegel]

Can someone explain this to me:
What is "The signal delay introduced between two synchronous nodes"? Only the signal delay between two nodes marked with 's' or the signal delay between two nodes not marked with 'a' (that means also between 'i' and 'o').
I am also wondering why in the text the message "Synchronous design ..." ends with period, and the sample output doesn't. What do I have to print?

[Adrian Kuegel]

I have now found the mistake in my program. The delay time is measured from a node marked with 'i' or 's' to a node marked with 'o' or 's'. Between these nodes there should only be nodes marked with 'a'.
The message should be printed with the period.

[epsilon0]

hello i'm working on 192, almost done. since the specs for this problem were not very clear, i'd appreciata some test data. thanks.

one of my question is what happens when there are "synchronous loops" i.e loops that have a synchronous node in them, how do you compute the longest path then? my thought is that you discard them, since the synchronous nodes get triggered once on clock edge and don't react to further changes on their inputs....

my other concern was wether a circuit could be assumed to be connex. in the sample input data one can see there's an unconnected input. what happens if the circuit is split in two parts, and one of them is not connected to any ouput but had an asynchronous loop... this shouldn't matter since it's not connected to outputs... i think i'm going too far in analysis there

[epsilon0]

if you look at 192, you can see the sample output does not match the expected output:

Output

For each circuit in the input file, your output file should contain a line with one of the following messages:

"Synchronous design. Maximum delay: <ss>." if the circuit has a synchronous design.

<ss> should be replaced by the longest delay found on any path between two synchronous nodes.

.....

Sample Output

Synchronous design. Maximum delay: 28

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

clearly the trailing dot is missing from the sample output. i think this is the reason why i got WA. so what is the correct specification for this problem???

[Ivan Golubev]

There must be a point after delay's value, i.e.
[c] if (nmax > ct)
printf("Clock period exceeded.\n");
else
printf("Synchronous design. Maximum delay: %d.\n", nmax);
[/c]

[epsilon0]

here's my source: i got WA

[c]#include <stdio.h>
#include <stdlib.h>

/* MAX macro */

#define MAX(a,b) ((a) > (b) ? (a) : (b))

/* node types */

#define INPUT 1
#define OUTPUT 2
#define SYNC 3
#define ASYNC 4

/* global stuff */

int *type;
int *delay;
int *network;
int n_nodes;


int has_cycle(int i, int *been_there)
{
int j;
int *been_there_too;
if (type != ASYNC)
return 0;
if (been_there)
return 1;
been_there_too = malloc(sizeof(int)*n_nodes);
memcpy(been_there_too,been_there,sizeof(int)*n_nodes);
been_there_too = 1;
for (j=0;j<n_nodes;j++)
if (network[n_nodes*i+j])
if (has_cycle(j, been_there_too))
{
free(been_there_too);
return 1;
}
free(been_there_too);
return 0;
}


int has_async_cycle()
{
int i;
int *been_there = malloc(sizeof(int)*n_nodes);
memset(been_there,0,sizeof(int)*n_nodes);
for (i=0;i<n_nodes;i++)
if (type == ASYNC)
if (has_cycle(i, been_there))
{
free(been_there);
return 1;
}
free(been_there);
return 0;
}


int longer(int i, int *been_there, int sum)
{
int j;
int max=0;
int tmp;
int *been_there_too;
if (been_there)
return 0;
if (type == OUTPUT)
return sum;
been_there_too = malloc(sizeof(int)*n_nodes);
memcpy(been_there_too,been_there,sizeof(int)*n_nodes);
been_there_too = 1;
if (type == ASYNC)
sum += delay;
for (j=0;j<n_nodes;j++)
if (network[n_nodes*i+j])
{
tmp = longer(j,been_there_too,sum);
max = MAX(max,tmp);
}
free(been_there_too);
return max;
}

int longer_path()
{
int i;
int max=0;
int tmp;
int *been_there = malloc(sizeof(int)*n_nodes);
memset(been_there,0,sizeof(int)*n_nodes);
for (i=0;i<n_nodes;i++)
if (type == INPUT)
{
tmp = longer(i,been_there,0);
max = MAX(max,tmp);
}
free(been_there);
return max;
}


int main()
{
int n_circuits;
int clock;
int n_wires;
int i,j;
int n1,n2;
char c;
int _longer;
scanf("%d\n",&n_circuits);
for (i=0;i<n_circuits;i++)
{
scanf("%d\n",&clock);
scanf("%d\n",&n_nodes);
type = malloc(sizeof(int)*n_nodes);
delay = malloc(sizeof(int)*n_nodes);
network = malloc(sizeof(int)*n_nodes*n_nodes);
memset(network,0,sizeof(int)*n_nodes*n_nodes);
for (j=0;j<n_nodes;j++)
{
scanf("%c %d\n",&c, &(delay[j]));
switch(c)
{
case 'i': type[j] = INPUT; break;
case 'o': type[j] = OUTPUT; break;
case 's': type[j] = SYNC; break;
case 'a': type[j] = ASYNC;
}
}
scanf("%d\n",&n_wires);
for (j=0;j<n_wires;j++)
{
scanf("%d %d\n",&n1,&n2);
network[n_nodes*n1+n2] = 1;
}
/* the work is done here */
if (has_async_cycle())
printf("Circuit contains cycle.\n");
else
if ((_longer = longer_path()) > clock)
printf("Clock period exceeded.\n");
else
printf("Synchronous design. Maximum delay: %d.\n",_longer);
/* done, clean and loop */
free(type);
free(delay);
free(network);
}
return 0;
}
[/c][/c]

[epsilon0]

hello,

i've programmed 192 last week, but it would get WA. i tested it a lot and it seems to give the right output in each case.

could you please give me special cases test data input/output or any trick there could be. thanx

[epsilon0]

see also my source code a few posts down the board:

http://acm.uva.es/board/viewtopic.php?t=1907

[sduval]

Hello,

Here is a simple set of data for problem 192 (Synchronous Design) :

1
30
11
i 0
i 0
i 0
i 0
i 0
o 0
a 2
a 7
s 0
a 4
a 10
12
0 7
1 10
2 10
3 6
4 6
10 7
7 8
10 8
6 9
8 9
9 5
9 10

and the corresponding output

Synchronous design. Maximum delay: 23.

Loops containing synchronous nodes should'nt be considered. You can't
pass through a synchronous node.
The circuit may not be connex.

Hope this help...

[riisiingsun]

can any one tell me what is the problem with my code? why it is showing output limit exceed?

[/code]
#include<stdio.h>

void main()
{
char ch,str1[2000000];
long int i;

while(scanf(" %[^\n]",str1)==1)
{
for(i=0;str1!=NULL;i++)
{
if(str1=='a' || str1=='A' || str1=='e'|| str1=='E' || str1=='i' || str1=='I' || str1=='o' || str1=='O' || str1=='u' || str1[i]=='U')
{
while((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
printf("%c",str1[i]);
i++;
}
i--;
printf("ay");
}

else if((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
ch=str1[i];
i++;
while((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
printf("%c",str1[i]);
i++;
}
i--;
printf("%cay",ch);
}
else
printf("%c",str1[i]);
}
printf("\n");
}
}

[metaphysis]

WA, can anyone give me some critical test data?

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INPUT = 0, OUTPUT = 1, SYN = 2, ASYN = 3;
const string typeText = "iosa";

struct vertex
{
	int index, delay, type;
};

vector < vertex > verties;
vector < int > parent, path;
vector < bool > discovered;
vector < vector < int > > edges;
int maximumDelay, maxNodes;
bool foundCycle = false;

void dfs(int start)
{
    if (foundCycle)
        return;

    discovered[start] = true;
    for (int i = 0; i < edges[start].size(); i++)
    {
        vertex v = verties[edges[start][i]];
        if (v.type == ASYN)
        {
            if (discovered[v.index] == false)
            {
                parent[v.index] = start;
                dfs(v.index);
            }
            else
            {
                if (parent[v.index] != start)
                {
                    foundCycle = true;
                    return;
                }
            }
        }
    }
}

bool findCycle()
{
    parent.clear();
    discovered.clear();
    
    parent.resize(verties.size());
    discovered.resize(verties.size());
    
    for (int i = 0; i < verties.size(); i++)
        if (verties[i].type == ASYN)
        {
            foundCycle = false;
            
            fill(parent.begin(), parent.end(), -1);
            fill(discovered.begin(), discovered.end(), false);
            
            dfs(i);
            
            if (foundCycle)
                return true;
        }
}

void forward(int v, int index)
{
    path[index] = v;
    
    if (index >= 1 && verties[path[index]].type != ASYN)
    {
        int tempMax = 0;       
        for (int i = 0; i <= index; i++)
            tempMax += verties[path[i]].delay;
        maximumDelay = max(tempMax, maximumDelay);
    }
    else
    {
        for (int i = 0; i < edges[v].size(); i++)
            forward(edges[v][i], index + 1);        
    }
}

void findMaximumDelay()
{
    path.resize(verties.size());
    maximumDelay = 0;
    for (int i = 0; i < verties.size(); i++)
        if (verties[i].type == INPUT || verties[i].type == SYN)
            forward(i, 0);
}

int main(int argc, char *argv[])
{
    int clock, circuits, delay, nodes, start, end, typeIndex;
    string type;
    
    cin >> circuits;
    while (circuits--)
    {
        cin >> clock >> nodes;
        
        verties.clear();
        edges.clear();
        edges.resize(nodes);
        
        for (int i = 0; i < nodes; i++)
        {
            cin >> type >> delay;
            typeIndex = (int)typeText.find(type);
            if (typeIndex == INPUT || typeIndex == OUTPUT || typeIndex == SYN)
                delay = 0;
            verties.push_back((vertex){i, delay, typeIndex});
        }
        
        int m;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            cin >> start >> end;
            edges[start].push_back(end);
        }
          
        if (findCycle())
            cout << "Circuit contains cycle." << endl;
        else 
        {
            findMaximumDelay();
            if (maximumDelay > clock)
                cout << "Clock period exceeded." << endl;
            else
                cout << "Synchronous design. Maximum delay: " << maximumDelay << "." << endl;
        }
    }
    
	return 0;
}

[metaphysis]

I found my mistake, DFS is not proper for finding cycle in directed graph.