1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
3
** This file is part of the Scotch software package for static mapping,
4
** graph partitioning and sparse matrix ordering.
6
** This software is governed by the CeCILL-C license under French law
7
** and abiding by the rules of distribution of free software. You can
8
** use, modify and/or redistribute the software under the terms of the
9
** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10
** URL: "http://www.cecill.info".
12
** As a counterpart to the access to the source code and rights to copy,
13
** modify and redistribute granted by the license, users are provided
14
** only with a limited warranty and the software's author, the holder of
15
** the economic rights, and the successive licensors have only limited
18
** In this respect, the user's attention is drawn to the risks associated
19
** with loading, using, modifying and/or developing or reproducing the
20
** software by the user in light of its specific status of free software,
21
** that may mean that it is complicated to manipulate, and that also
22
** therefore means that it is reserved for developers and experienced
23
** professionals having in-depth computer knowledge. Users are therefore
24
** encouraged to load and test the software's suitability as regards
25
** their requirements in conditions enabling the security of their
26
** systems and/or data to be ensured and, more generally, to use and
27
** operate it in the same conditions as regards security.
29
** The fact that you are presently reading this means that you have had
30
** knowledge of the CeCILL-C license and that you accept its terms.
32
/************************************************************/
34
/** NAME : arch_torus.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module handles the torus graph **/
39
/** target architectures. **/
41
/** DATES : # Version 0.0 : from : 01 dec 1992 **/
42
/** to : 24 mar 1993 **/
43
/** # Version 1.2 : from : 04 feb 1994 **/
44
/** to : 11 feb 1994 **/
45
/** # Version 1.3 : from : 20 apr 1994 **/
46
/** to : 20 apr 1994 **/
47
/** # Version 2.0 : from : 06 jun 1994 **/
48
/** to : 23 dec 1994 **/
49
/** # Version 2.1 : from : 07 apr 1995 **/
50
/** to : 29 jun 1995 **/
51
/** # Version 3.0 : from : 01 jul 1995 **/
52
/** to 08 sep 1995 **/
53
/** # Version 3.1 : from : 07 may 1996 **/
54
/** to 22 jul 1996 **/
55
/** # Version 3.2 : from : 16 oct 1996 **/
56
/** to 14 may 1998 **/
57
/** # Version 3.3 : from : 01 oct 1998 **/
58
/** to 01 oct 1998 **/
59
/** # Version 4.0 : from : 05 nov 2003 **/
60
/** to 10 mar 2005 **/
62
/************************************************************/
65
** The defines and includes.
73
#include "arch_torus.h"
75
/***********************************************/
77
/* These are the 2-dimensional torus routines. */
79
/***********************************************/
81
/* This routine loads the
82
** bidimensional torus architecture.
84
** - 0 : if the architecture has been successfully read.
90
ArchTorus2 * restrict const archptr,
91
FILE * restrict const stream)
93
#ifdef SCOTCH_DEBUG_ARCH1
94
if ((sizeof (ArchTorus2) > sizeof (ArchDummy)) ||
95
(sizeof (ArchTorus2Dom) > sizeof (ArchDomDummy))) {
96
errorPrint ("archTorus2ArchLoad: invalid type specification");
99
#endif /* SCOTCH_DEBUG_ARCH1 */
101
if ((intLoad (stream, &archptr->c[0]) +
102
intLoad (stream, &archptr->c[1]) != 2) ||
103
(archptr->c[0] < 1) || (archptr->c[1] < 1)) {
104
errorPrint ("archTorus2ArchLoad: bad input");
111
/* This routine saves the
112
** bidimensional torus architecture.
114
** - 0 : if the architecture has been successfully written.
120
const ArchTorus2 * const archptr,
121
FILE * restrict const stream)
123
#ifdef SCOTCH_DEBUG_ARCH1
124
if ((sizeof (ArchTorus2) > sizeof (ArchDummy)) ||
125
(sizeof (ArchTorus2Dom) > sizeof (ArchDomDummy))) {
126
errorPrint ("archTorus2ArchSave: invalid type specification");
129
#endif /* SCOTCH_DEBUG_ARCH1 */
131
if (fprintf (stream, "%ld %ld ",
132
(long) archptr->c[0],
133
(long) archptr->c[1]) == EOF) {
134
errorPrint ("archTorus2ArchSave: bad output");
141
/* This function returns the smallest number
142
** of terminal domain included in the given
148
const ArchTorus2 * const archptr,
149
const ArchTorus2Dom * const domptr)
151
return ((domptr->c[1][0] * archptr->c[0]) + domptr->c[0][0]); /* Return vertex number */
154
/* This function returns the terminal domain associated
155
** with the given terminal number in the architecture.
157
** - 0 : if label is valid and domain has been updated.
158
** - 1 : if label is invalid.
164
const ArchTorus2 * const archptr,
165
ArchTorus2Dom * const domptr,
166
const ArchDomNum domnum)
168
if (domnum < (archptr->c[0] * archptr->c[1])) { /* If valid label */
169
domptr->c[0][0] = /* Set the domain */
170
domptr->c[0][1] = domnum % archptr->c[0];
172
domptr->c[1][1] = domnum / archptr->c[0];
177
return (1); /* Cannot set domain */
180
/* This function returns the number of
181
** elements in the rectangular domain.
186
const ArchTorus2 * const archptr,
187
const ArchTorus2Dom * const domptr)
189
return ((domptr->c[0][1] - domptr->c[0][0] + 1) *
190
(domptr->c[1][1] - domptr->c[1][0] + 1));
193
/* This function returns the average
194
** distance between two rectangular
195
** domains (in fact the distance between
196
** the centers of the domains).
201
const ArchTorus2 * const archptr,
202
const ArchTorus2Dom * const dom0ptr,
203
const ArchTorus2Dom * const dom1ptr)
207
dx = abs (dom0ptr->c[0][0] + dom0ptr->c[0][1] -
208
dom1ptr->c[0][0] - dom1ptr->c[0][1]);
209
dx = (dx > archptr->c[0])
210
? archptr->c[0] - (dx / 2)
213
dy = abs (dom0ptr->c[1][0] + dom0ptr->c[1][1] -
214
dom1ptr->c[1][0] - dom1ptr->c[1][1]);
215
dy = (dy > archptr->c[1])
216
? archptr->c[1] - (dy / 2)
222
/* This function sets the biggest
223
** domain available for this
232
const ArchTorus2 * const archptr,
233
ArchTorus2Dom * restrict const domptr)
237
domptr->c[0][1] = archptr->c[0] - 1;
238
domptr->c[1][1] = archptr->c[1] - 1;
243
/* This routine reads domain information
244
** from the given stream.
252
const ArchTorus2 * const archptr,
253
ArchTorus2Dom * restrict const domptr,
254
FILE * restrict const stream)
256
if (intLoad (stream, &domptr->c[0][0]) +
257
intLoad (stream, &domptr->c[1][0]) +
258
intLoad (stream, &domptr->c[0][1]) +
259
intLoad (stream, &domptr->c[1][1]) != 4) {
260
errorPrint ("archTorus2DomLoad: bad input");
267
/* This routine saves domain information
268
** to the given stream.
275
const ArchTorus2 * const archptr,
276
const ArchTorus2Dom * const domptr,
277
FILE * restrict const stream)
279
if (fprintf (stream, "%ld %ld %ld %ld ",
280
(long) domptr->c[0][0], (long) domptr->c[1][0],
281
(long) domptr->c[0][1], (long) domptr->c[1][1]) == EOF) {
282
errorPrint ("archTorus2DomSave: bad output");
289
/* This function tries to split a rectangular
290
** domain into two subdomains.
292
** - 0 : if bipartitioning succeeded.
293
** - 1 : if bipartitioning could not be performed.
298
archTorus2DomBipart (
299
const ArchTorus2 * const archptr,
300
const ArchTorus2Dom * const domptr,
301
ArchTorus2Dom * restrict const dom0ptr,
302
ArchTorus2Dom * restrict const dom1ptr)
304
if ((domptr->c[0][0] == domptr->c[0][1]) && /* Return if cannot bipartition more */
305
(domptr->c[1][0] == domptr->c[1][1]))
308
if ((domptr->c[0][1] - domptr->c[0][0]) > /* Split domain in two along largest dimension */
309
(domptr->c[1][1] - domptr->c[1][0])) {
310
dom0ptr->c[0][0] = domptr->c[0][0];
311
dom0ptr->c[0][1] = (domptr->c[0][0] + domptr->c[0][1]) / 2;
312
dom1ptr->c[0][0] = dom0ptr->c[0][1] + 1;
313
dom1ptr->c[0][1] = domptr->c[0][1];
314
dom0ptr->c[1][0] = dom1ptr->c[1][0] = domptr->c[1][0];
315
dom0ptr->c[1][1] = dom1ptr->c[1][1] = domptr->c[1][1];
318
dom0ptr->c[0][0] = dom1ptr->c[0][0] = domptr->c[0][0];
319
dom0ptr->c[0][1] = dom1ptr->c[0][1] = domptr->c[0][1];
320
dom0ptr->c[1][0] = domptr->c[1][0];
321
dom0ptr->c[1][1] = (domptr->c[1][0] + domptr->c[1][1]) / 2;
322
dom1ptr->c[1][0] = dom0ptr->c[1][1] + 1;
323
dom1ptr->c[1][1] = domptr->c[1][1];
329
/***********************************************/
331
/* These are the 3-dimensional torus routines. */
333
/***********************************************/
335
/* This routine loads the
336
** tridimensional torus architecture.
338
** - 0 : if the architecture has been successfully read.
344
ArchTorus3 * restrict const archptr,
345
FILE * restrict const stream)
347
#ifdef SCOTCH_DEBUG_ARCH1
348
if ((sizeof (ArchTorus3) > sizeof (ArchDummy)) ||
349
(sizeof (ArchTorus3Dom) > sizeof (ArchDomDummy))) {
350
errorPrint ("archTorus3ArchLoad: invalid type specification");
353
#endif /* SCOTCH_DEBUG_ARCH1 */
355
if ((intLoad (stream, &archptr->c[0]) +
356
intLoad (stream, &archptr->c[1]) +
357
intLoad (stream, &archptr->c[2]) != 3) ||
358
(archptr->c[0] < 1) || (archptr->c[1] < 1) || (archptr->c[2] < 1)) {
359
errorPrint ("archTorus3ArchLoad: bad input");
366
/* This routine saves the
367
** tridimensional torus architecture.
369
** - 0 : if the architecture has been successfully written.
375
const ArchTorus3 * const archptr,
376
FILE * restrict const stream)
378
#ifdef SCOTCH_DEBUG_ARCH1
379
if ((sizeof (ArchTorus3) > sizeof (ArchDummy)) ||
380
(sizeof (ArchTorus3Dom) > sizeof (ArchDomDummy))) {
381
errorPrint ("archTorus3ArchSave: invalid type specification");
384
#endif /* SCOTCH_DEBUG_ARCH1 */
386
if (fprintf (stream, "%ld %ld %ld ",
387
(long) archptr->c[0], (long) archptr->c[1], (long) archptr->c[2]) == EOF) {
388
errorPrint ("archTorus3ArchSave: bad output");
395
/* This function returns the smallest number
396
** of terminal domain included in the given
402
const ArchTorus3 * const archptr,
403
const ArchTorus3Dom * const domptr)
405
return ((((domptr->c[2][0] * archptr->c[1]) + /* Return the vertex number */
406
domptr->c[1][0]) * archptr->c[0]) +
410
/* This function returns the terminal domain associated
411
** with the given terminal number in the architecture.
413
** - 0 : if label is valid and domain has been updated.
414
** - 1 : if label is invalid.
420
const ArchTorus3 * const archptr,
421
ArchTorus3Dom * const domptr,
422
const ArchDomNum domnum)
424
if (domnum < (archptr->c[0] * archptr->c[1] * archptr->c[2])) { /* If valid label */
425
domptr->c[0][0] = /* Set the domain */
426
domptr->c[0][1] = domnum % archptr->c[0];
428
domptr->c[1][1] = (domnum / archptr->c[0]) % archptr->c[1];
430
domptr->c[2][1] = domnum / (archptr->c[0] * archptr->c[1]);
435
return (1); /* Cannot set domain */
438
/* This function returns the number of
439
** elements in the cubic domain.
444
const ArchTorus3 * const archptr,
445
const ArchTorus3Dom * const domptr)
447
return ((domptr->c[0][1] - domptr->c[0][0] + 1) *
448
(domptr->c[1][1] - domptr->c[1][0] + 1) *
449
(domptr->c[2][1] - domptr->c[2][0] + 1));
452
/* This function returns the average distance
453
** between two cubic domains (in fact the
454
** distance between the centers of the domains).
459
const ArchTorus3 * const archptr,
460
const ArchTorus3Dom * const dom0ptr,
461
const ArchTorus3Dom * const dom1ptr)
465
dc = abs (dom0ptr->c[0][0] + dom0ptr->c[0][1] -
466
dom1ptr->c[0][0] - dom1ptr->c[0][1]);
467
ds = (dc > archptr->c[0])
468
? archptr->c[0] - (dc / 2)
471
dc = abs (dom0ptr->c[1][0] + dom0ptr->c[1][1] -
472
dom1ptr->c[1][0] - dom1ptr->c[1][1]);
473
ds += (dc > archptr->c[1])
474
? archptr->c[1] - (dc / 2)
477
dc = abs (dom0ptr->c[2][0] + dom0ptr->c[2][1] -
478
dom1ptr->c[2][0] - dom1ptr->c[2][1]);
479
ds += (dc > archptr->c[2])
480
? archptr->c[2] - (dc / 2)
486
/* This function sets the biggest
487
** domain available for this
496
const ArchTorus3 * const archptr,
497
ArchTorus3Dom * restrict const domptr)
502
domptr->c[0][1] = archptr->c[0] - 1;
503
domptr->c[1][1] = archptr->c[1] - 1;
504
domptr->c[2][1] = archptr->c[2] - 1;
509
/* This routine reads domain information
510
** from the given stream.
518
const ArchTorus3 * const archptr,
519
ArchTorus3Dom * restrict const domptr,
520
FILE * restrict const stream)
522
if (intLoad (stream, &domptr->c[0][0]) +
523
intLoad (stream, &domptr->c[1][0]) +
524
intLoad (stream, &domptr->c[2][0]) +
525
intLoad (stream, &domptr->c[0][1]) +
526
intLoad (stream, &domptr->c[1][1]) +
527
intLoad (stream, &domptr->c[2][1]) != 6) {
528
errorPrint ("archTorus3DomLoad: bad input");
535
/* This routine saves domain information
536
** to the given stream.
544
const ArchTorus3 * const archptr,
545
const ArchTorus3Dom * const domptr,
546
FILE * restrict const stream)
548
if (fprintf (stream, "%ld %ld %ld %ld %ld %ld ",
549
(long) domptr->c[0][0], (long) domptr->c[1][0], (long) domptr->c[2][0],
550
(long) domptr->c[0][1], (long) domptr->c[1][1], (long) domptr->c[2][1]) == EOF) {
551
errorPrint ("archTorus3DomSave: bad output");
558
/* This function tries to split a cubic
559
** domain into two subdomains.
561
** - 0 : if bipartitioning succeeded.
562
** - 1 : if bipartitioning could not be performed.
567
archTorus3DomBipart (
568
const ArchTorus3 * const archptr,
569
const ArchTorus3Dom * const domptr,
570
ArchTorus3Dom * restrict const dom0ptr,
571
ArchTorus3Dom * restrict const dom1ptr)
575
if ((domptr->c[0][0] == domptr->c[0][1]) && /* Return if cannot bipartition more */
576
(domptr->c[1][0] == domptr->c[1][1]) &&
577
(domptr->c[2][0] == domptr->c[2][1]))
580
i = ((domptr->c[1][1] - domptr->c[1][0]) > /* Find largest dimension */
581
(domptr->c[0][1] - domptr->c[0][0]))
583
if ((domptr->c[2][1] - domptr->c[2][0]) >
584
(domptr->c[i][1] - domptr->c[i][0]))
587
if (i == 0) { /* Split domain in two along largest dimension */
588
dom0ptr->c[0][0] = domptr->c[0][0];
589
dom0ptr->c[0][1] = (domptr->c[0][0] + domptr->c[0][1]) / 2;
590
dom1ptr->c[0][0] = dom0ptr->c[0][1] + 1;
591
dom1ptr->c[0][1] = domptr->c[0][1];
593
dom0ptr->c[1][0] = dom1ptr->c[1][0] = domptr->c[1][0];
594
dom0ptr->c[1][1] = dom1ptr->c[1][1] = domptr->c[1][1];
596
dom0ptr->c[2][0] = dom1ptr->c[2][0] = domptr->c[2][0];
597
dom0ptr->c[2][1] = dom1ptr->c[2][1] = domptr->c[2][1];
600
dom0ptr->c[0][0] = dom1ptr->c[0][0] = domptr->c[0][0];
601
dom0ptr->c[0][1] = dom1ptr->c[0][1] = domptr->c[0][1];
603
dom0ptr->c[1][0] = domptr->c[1][0];
604
dom0ptr->c[1][1] = (domptr->c[1][0] + domptr->c[1][1]) / 2;
605
dom1ptr->c[1][0] = dom0ptr->c[1][1] + 1;
606
dom1ptr->c[1][1] = domptr->c[1][1];
608
dom0ptr->c[2][0] = dom1ptr->c[2][0] = domptr->c[2][0];
609
dom0ptr->c[2][1] = dom1ptr->c[2][1] = domptr->c[2][1];
612
dom0ptr->c[0][0] = dom1ptr->c[0][0] = domptr->c[0][0];
613
dom0ptr->c[0][1] = dom1ptr->c[0][1] = domptr->c[0][1];
615
dom0ptr->c[1][0] = dom1ptr->c[1][0] = domptr->c[1][0];
616
dom0ptr->c[1][1] = dom1ptr->c[1][1] = domptr->c[1][1];
618
dom0ptr->c[2][0] = domptr->c[2][0];
619
dom0ptr->c[2][1] = (domptr->c[2][0] + domptr->c[2][1]) / 2;
620
dom1ptr->c[2][0] = dom0ptr->c[2][1] + 1;
621
dom1ptr->c[2][1] = domptr->c[2][1];
added
removed
src/libscotch/arch_torus.c
