Hi, i have collected the following error when simulating a Minimun
Spanning Tree solver:
############################################################################
2 XACT CONSISTENCY CHECKER: FAILED 0x[0x3c023d80, line 0x3c023d80]
ACCESS TYPE: LD IN WRITE SET OF 10
2 XACT CONSISTENCY CHECK FAILURE DUE TO OVERLAP BETWEEN ESCAPE ACTIONS
AND TRANSACTIONS Address: [0x3c023d80, line 0x3c023d80] PC: [0x12b70,
line 0x12b40]
2 XACT CONSISTENCY CHECKER: FAILED 0x[0x3c023d80, line 0x3c023d80]
ACCESS TYPE: LD_XACT IN WRITE SET OF 10
simics-common: log_tm/TransactionSimicsProcessor.C:399: void
TransactionSimicsProcessor::xactIsolationCheck(memory_transaction_t*,
CacheRequestType): Assertion `false' failed.
Abort (SIGABRT) in main thread
The simulation state has been corrupted. Simulation cannot continue.
Please restart Simics.
[0] Makegraph. Transaccion Command aborted
Starting command line. (May have skipped commands in script files.)
fork failed: Cannot allocate memory
Unable to start readhist; only limited command line editing available
[cpu2] v:0x0000000000011d7c p:0x0003ed11d7c lduw [%l3 + 428], %o4
Setting new inspection cpu: cpu2
simics> Traceback (most recent call last):
File "../../../gen-scripts/mfacet.py", line 308, in
console_branch_internal
wait_for_string(get_console(), __prompt)
File
"/opt/virtutech/simics-3.0.29/x86-linux/lib/python/text_console_common.py",
line 10, in wait_for_string
wait_for_obj_hap("Xterm_Break_String", obj, break_id)
File "/opt/virtutech/simics-3.0.29/x86-linux/lib/python/cli_impl.py",
line 3374, in wait_for_obj_hap
return wait_for_hap_common([hap_name, name, idx0])
File "/opt/virtutech/simics-3.0.29/x86-linux/lib/python/cli_impl.py",
line 3352, in wait_for_hap_common
raise SimExc_Break, "Script branch interrupted"
sim_core.SimExc_Break: Script branch interrupted
Exception in python branch
############################################################################
The code i have simulated is the next:
##########################################################
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
/**********#include "txlocks.h"**********/
#include "transaction.h"
#define CONST_m1 10000
#define CONST_b 31415821
#define RANGE 2048
/* Edge data structure of the input graph */
typedef struct edge_st {
unsigned int vert;
int dist;
struct edge_st *next;
} *Edge;
/* Vertex data structure of the input graph */
typedef struct vert_st {
int vid;
int mindist;
int minvid;
Edge edg;
struct vert_st *next;
} *Vertex;
/* Auxiliary vertex data structure */
typedef struct vertex_pos {
Vertex vertexptr;
int vertexidx;
} VertexPos;
int vid_cnt = 0;
/* Input graph: Complete weighted undirected graph */
Vertex *graph;
int gsize = 0; /* number of vertices */
Vertex mst_vertex = NULL;
Vertex mst_vertexR = NULL;
int insertion_cnt;
/* Output MST */
Vertex *mst;
/* Number of threads */
int num_threads;
/* Other shared variables */
VertexPos vertpos_g;
int first_reduc;
extern volatile int sense; /*Definida en ../common/transcation.c*/
/* pThreads variables */
pthread_attr_t pthread_custom_attr;
/*pthread_barrier_t barr;*/
static int mult(int p, int q)
{
int p1, p0, q1, q0;
p1 = p/CONST_m1;
p0 = p%CONST_m1;
q1 = q/CONST_m1;
q0 = q%CONST_m1;
return (((p0*q1+p1*q0)%CONST_m1)*CONST_m1+p0*q0);
}
static int d_rand(int seed)
{
int tmp;
tmp = (mult(seed,CONST_b)+1);
return tmp;
}
static int compute_dist(int i, int j, int numvert)
{
int less, gt;
if (i < j)
{
less = i;
gt = j;
}
else
{
less = j;
gt = i;
}
return (d_rand(less*numvert+gt)%RANGE)+1;
}
/* Insert an edge in the edge list of the graph */
void EdgeInsert(Vertex vorg,Edge edg)
{
Edge tmp, tmpp;
tmpp = tmp = vorg->edg;
if (tmp != NULL)
{
tmp = tmp->next;
while (tmp != NULL)
{
tmpp = tmpp->next;
tmp = tmp->next;
}
tmpp->next = edg;
}
else vorg->edg = edg;
}
/* Insert a vertex in the vertex list of the graph */
void VertexInsert(Vertex ver)
{
Vertex tmp,tmpp;
if (*graph == NULL) *graph = ver;
else
{
tmpp = *graph;
tmp = tmpp->next;
while (tmp != NULL)
{
tmpp = tmpp->next;
tmp = tmp->next;
}
tmpp->next = ver;
}
}
/* Get a vertex from the vertex list */
VertexPos VertexGet()
{
VertexPos vp;
if (vertpos_g.vertexptr != NULL)
{
if (vertpos_g.vertexptr == (Vertex) -1)
{
vertpos_g.vertexptr = *graph;
vertpos_g.vertexidx = 0;
}
else
{
vertpos_g.vertexptr = vertpos_g.vertexptr->next;
vertpos_g.vertexidx++;
}
}
vp.vertexptr = vertpos_g.vertexptr;
vp.vertexidx = vertpos_g.vertexidx;
return vp;
}
/* Vertex block partitioning of the graph */
void GraphPartition(int myid,int tsize)
{
Vertex tmp, tmpp;
int count, local_sense = sense;
/*printf("[%d] GraphPartition phase 1: Vertex block
partitioning\n",myid);*/
tmpp = tmp = *graph;
count = myid * tsize;
if (count)
{
tmp = tmp->next;
count--;
}
while (count-- > 0)
{
tmp = tmp->next;
tmpp = tmpp->next;
}
*(graph+myid) = tmp;
/* printf("[%d] *(graph+%d) 0x%x\n",myid,myid,*(graph+myid)); */
/* Threads waiting until graph partitioned */
/*pthread_barrier_wait(&barr);*/
Barrier_non_breaking(&local_sense, myid, num_threads);
/* printf("[%d] GraphPartition phase 2: Isolating subgraphs\n",myid); */
if (tmpp != tmp) tmpp->next = NULL;
/*printf("[%d] GraphPartition done.\n",myid);*/
}
/* Making the input graph in parallel (vertex parallelism) */
void MakeGraph(int myid,int tsize)
{
Vertex ver, tmp;
VertexPos vp;
Edge edg;
int dist;
int i, local_sense=sense;
/*printf("[%d] MakeGraph phase 1: Vertices (%d verts per
thread)\n",myid,tsize);*/
/* Creating in parallel the vertex list */
for (i=0; i<tsize; i++)
{
ver = (Vertex) malloc(sizeof(*ver));
ver->mindist = 9999999;
ver->minvid = 0;
ver->edg = NULL;
ver->next = NULL;
BEGIN_TRANSACTION(0);
ver->vid = vid_cnt++;
VertexInsert(ver);
COMMIT_TRANSACTION(0);
}
/* Threads waiting until all vertices built */
/*pthread_barrier_wait(&barr);*/
Barrier_non_breaking(&local_sense, myid, num_threads);
tmp = *graph;
i=0;
while(tmp!=NULL){ tmp = tmp->next; i++;}
printf("[%d] Mis %d vertices creados.Total:%d\n", myid, tsize,i);
/* printf("[%d] MakeGraph phase 2: Edges\n",myid); */
/* Creating the edge list in parallel for each vertex */
BEGIN_TRANSACTION(1);
vp = VertexGet();
COMMIT_TRANSACTION(1);
while (vp.vertexptr != NULL)
{
for (ver=*graph,i=0; ver!=NULL; ver=ver->next,i++)
{
if (i != vp.vertexidx)
{
dist = compute_dist(i,vp.vertexidx,num_threads*tsize);
edg = (Edge) malloc(sizeof(*edg));
edg->vert = (unsigned int) ver;
edg->dist = dist;
edg->next = NULL;
EdgeInsert(vp.vertexptr,edg);
/*printf("[%d] Edge orig 0x%x dest 0x%x dist
%d\n",myid,vp.vertexptr,ver,dist);*/
}
}
printf("[%d] Makegraph. Transaccion inicio\n",myid);
BEGIN_TRANSACTION(2);
vp = VertexGet();
COMMIT_TRANSACTION(2);
printf("[%d] Makegraph. Transaccion final\n",myid);
}
/* printf("[%d] MakeGraph done\n",myid); */
}
/* Obtaining weight of the edge between two vertices */
int distance(Vertex ver, Vertex vref)
{
Edge edge;
Vertex v;
int done = 0;
edge = ver->edg;
while (!done)
{
if (edge == NULL) done = 2;
else if (vref == (Vertex) edge->vert) done = 1;
else edge = edge->next;
}
if (done == 2) return 0;
else return edge->dist;
}
/* Obtaining the nearest vertex in a subgraph */
Vertex mstVertexExtract(int myid, Vertex ver, Vertex vref)
{
Vertex retval;
Vertex tmp, prev;
int dist,dist2;
/* printf("[%d] ver 0x%x vref 0x%x\n",myid,ver,vref); */
/* If the subgraph is null return an invalid vertex */
if (!ver)
{
retval = (Vertex) malloc (sizeof(*retval));
retval->mindist = 999999;
retval->minvid = 0;
return retval;
}
/* Select the first vertex in the subgraph as the default nearest one */
retval = ver;
dist = distance(ver,vref);
if (dist)
{
if (dist < retval->mindist)
{
retval->mindist = dist;
retval->minvid = vref->vid;
}
}
else printf("[%d] FAIL: Vertex not found\n",myid);
/* Check the rest of the vertices in the subgraph and select the
nearest one */
prev = ver;
for (tmp=ver->next; tmp; prev=tmp,tmp=tmp->next)
{
if (tmp == vref)
{
Vertex next;
next = tmp->next;
prev->next = next;
}
else
{
dist2 = tmp->mindist;
dist = distance(tmp,vref);
/* printf("[%d] Found dist %d from inserted 0x%x to vertex 0x%x
(tmp)\n",dist,inserted,tmp); */
if (dist)
{
if (dist < dist2)
{
tmp->mindist = dist;
tmp->minvid = vref->vid;
dist2 = dist;
}
}
else printf("[%d] FAIL: Vertex not found\n",myid);
if (dist2 < retval->mindist) retval = tmp;
}
}
/* printf("[%d] mstVE: ver 0x%x vref 0x%x retval 0x%x retval->mindist
%d\n",myid,ver,vref,retval,retval->mindist); */
return retval;
}
/* Insert a new node in the MST */
void mstInsert(Vertex ver, Vertex *mstv)
{
Vertex tmp, tmpp, tmppp;
insertion_cnt++;
tmppp = NULL;
tmpp = *mst;
tmp = tmpp->next;
while (tmp != NULL)
{
if (tmppp == NULL) tmppp = *mst;
else tmppp = tmppp->next;
tmpp = tmpp->next;
tmp = tmp->next;
}
if (insertion_cnt == 1)
{
/* The first thread append the new locally nearest node */
tmpp->next = (Vertex) malloc(sizeof(*tmpp));
tmp = tmpp->next;
tmp->vid = ver->vid;
tmp->mindist = ver->mindist;
tmp->minvid = ver->minvid;
tmp->next = NULL;
*mstv = ver;
}
else
{
/* The rest of threads compare their node with the appended one and
replaced it if nearer */
if (ver->mindist < tmpp->mindist)
{
tmppp->next = (Vertex) malloc(sizeof(*tmpp));
tmp = tmppp->next;
tmp->vid = ver->vid;
tmp->mindist = ver->mindist;
tmp->minvid = ver->minvid;
tmp->next = NULL;
*mstv = ver;
}
}
if (insertion_cnt == num_threads) insertion_cnt = 0;
}
/* Computes an MST from the input graph using a greedy approach */
void ComputeMst(int myid, int tsize)
{
Vertex ver, trv;
int i/*, sense, sense_r*/, local_sense=sense, senseRev;
/* printf("[%d] Compute MST phase 1: Inserting first (arbitrary)
vertex of MST\n",myid); */
/* Select an arbitrary vertex as the root of the MST */
insertion_cnt = 0;
gsize = tsize*num_threads;
ver = *(graph+myid);
if (myid == 0)
{
*mst = (Vertex) malloc(sizeof(*ver));
(*mst)->vid = ver->vid;
(*mst)->mindist = 0;
(*mst)->minvid = 0;
(*mst)->next = NULL;
mst_vertex = ver;
/* printf("[%d] ver 0x%x mindist %d\n",myid,ver,(*mst)->mindist); */
ver = ver->next;
tsize--;
}
/*printf("[%d] ver 0x%x mst_vertex 0x%x
0x%x\n",myid,ver,mst_vertex,mst_vertexR);*/
/* Threads start together computing a MST */
/*pthread_barrier_wait(&barr);*/
Barrier_non_breaking(&local_sense, myid, num_threads);
/* printf("[%d] Compute MST phase 2\n",myid); */
/* Find next vertex in the MST using a one-by-one approach (greedy) */
/* Use a sense reversal technique to avoid two barrier fences */
for (i=0, senseRev=1; i<gsize-1; i++)
{
if (senseRev)
{
if (mst_vertex == ver) ver = ver->next;
trv = mstVertexExtract(myid,ver,mst_vertex);
}
else
{
if (mst_vertexR == ver) ver = ver->next;
trv = mstVertexExtract(myid,ver,mst_vertexR);
}
/* printf("[%d] i %d trv 0x%x\n",myid,i,trv); */
BEGIN_TRANSACTION(3);
if (senseRev) mstInsert(trv, &mst_vertexR);
else mstInsert(trv, &mst_vertex);
COMMIT_TRANSACTION(3);
Barrier_non_breaking(&local_sense, myid, num_threads);
/*pthread_barrier_wait(&barr);*/
senseRev = !senseRev;
}
}
/* Main parallel routine */
void *Graph_MST(void *tid)
{
int myid;
int tsize;
int local_sense = sense;
/*time_t stime1, etime1;
time_t stime2, etime2;
time_t stime3, etime3;*/
myid = *((int*) tid);
tm_bind_to_cabinet(myid+1);
Barrier_breaking(&local_sense, myid, num_threads);
set_transaction_registers(myid);
tsize = gsize/num_threads;
BEGIN_WORKLOAD_TRANSACTION;
/* Computing input graph */
printf("[%d] Making graph of size %d\n",myid,gsize);
/*stime1 = time(NULL);*/
MakeGraph(myid,tsize);
/*etime1 = time(NULL);*/
printf("[%d] Graph created.\n", myid);
/* Partitioning input graph */
/* printf("[%d] Partition graph across threads\n",myid); */
/*stime2 = time(NULL);*/
GraphPartition(myid,tsize);
/*etime2 = time(NULL);*/
/*printf("[%d] Graph partitioned. Time: %f s.\n", myid,
difftime(etime2, stime2));*/
/* Put magic call here to simulate the MST computing only */
/* NEW_RUBY_MAGIC_CALL(3) */
/* Computing a MST of the input graph */
/* printf("[%d] Computing MST of graph\n",myid); */
/*stime3 = time(NULL);*/
ComputeMst(myid,tsize);
/*etime3 = time(NULL);*/
/*printf("[%d] MST computed. Time: %f s.\n", myid, difftime(etime3,
stime3));*/
/* printf("[%d] Times: %lld %lld
%lld\n",myid,etime1-stime1,etime2-stime2,etime3-stime3); */
END_WORKLOAD_TRANSACTION;
Barrier_breaking(&local_sense, myid, num_threads);
}
int main(int argc, char *argv[])
{
Vertex ver;
/* Thread parameters */
pthread_t *threads;
int *ids;
int i, mst_weight;
/*time_t stime, etime;*/
/* Command line arguments processing */
if (argc > 2) num_threads = atoi(argv[2]);
else num_threads = 1;
if (argc > 1) gsize = atoi(argv[1]);
else gsize = 1024;
printf("[%d] Computing a MST of a graph using the Prim-Dijkstra
algorithm\n",-1);
/* Thread initializations */
init_transaction_state(num_threads);
threads = (pthread_t *) malloc(num_threads*sizeof(*threads));
ids = (int *) calloc(num_threads, sizeof(int));
pthread_attr_init(&pthread_custom_attr);
pthread_attr_setscope(&pthread_custom_attr, PTHREAD_SCOPE_SYSTEM);
/*pthread_barrier_init(&barr,NULL,num_threads);*/
/* Graph initializations */
graph = (Vertex *) malloc(num_threads*sizeof(*graph));
for (i=0; i<num_threads; i++) *(graph+i) = NULL;
mst = (Vertex *) malloc(sizeof(*mst));
*mst = NULL;
vertpos_g.vertexptr = (Vertex) -1;
vertpos_g.vertexidx = -1;
mst_vertex = (Vertex) malloc(sizeof(*mst_vertex));
/* Creating threads */
/*stime = time(NULL);*/
for (i=0; i<num_threads-1; i++)
{
ids[i] = i;
pthread_create(&threads[i], &pthread_custom_attr, Graph_MST, (void
*)(ids+i));
}
ids[i] = i;
Graph_MST(ids+i);
for (i=0; i<num_threads-1; i++)
{
pthread_join(threads[i], NULL);
}
/*etime = time(NULL);*/
ver = *mst;
mst_weight = ver->mindist;
ver = ver->next;
while (ver != NULL)
{
mst_weight += ver->mindist;
/* printf("[%d] MST: Org %d Dst %d (weg
%d)\n",-1,ver->vid,ver->minvid,ver->mindist); */
ver = ver->next;
}
printf("[%d] MST done with weight %d \n",-1,mst_weight);
}
##########################################################
Could anybody tell me what is going wrong?
Sorry for the long message.
Regards and thanks in advance, Ricardo Quislant.
|