|| || || || || || || ||

---

PxPartition.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2003-2004, University of Amsterdam, The Netherlands.
 *  All rights reserved.
 *
 *  Author(s):
 *  Frank Seinstra <fjseins@wins.uva.nl>
 */

#ifndef __PxPartition_h_
#define __PxPartition_h_


#include "Core/Array/Pattern/PxSystem.h"

namespace Impala
{
namespace Core
{
namespace Array
{
namespace Pattern
{


/**********************************************************************/
/*** The partitioning routines below define which compute node is   ***/
/*** responsible for which part of an array data structure, EXCLU-  ***/
/*** DING ANY POTENTIAL BORDER INFORMATION!                         ***/
/*** In this implementation, the responsibilities are dependent on  ***/
/*** the number of compute nodes that are available, how the nodes  ***/
/*** are logically connected and how the array data is mapped onto  ***/
/*** the logical 3D grid formed by the compute nodes.               ***/
/*** Here, the grid of compute nodes is formed  based on the three  ***/
/*** parameters to 'PxInitPartition(..)' that represent the number  ***/
/*** of compute nodes in each of the grid's 3 dimensions ('xcpus',  ***/
/*** 'ycpus', and 'zcpus').                                         ***/
/***                                                                ***/
/*** [see: PxInitPartition(), PxRePartition(),                      ***/
/***       PxLogPartXcpus(), PxLogPartYcpus(), PxLogPartZcpus()]    ***/
/***                                                                ***/
/*** The total number of CPUs (nrCPUs) used is given by:            ***/
/***                                                                ***/
/***                nrCPUs = xCPUs * yCPUs * zCPUs                  ***/
/***                                                                ***/
/*** Each node has a unique number from the set of consecutive in-  ***/
/*** tegers in the range: 0 .. nrCPUs-1.                            ***/
/*** Nodes are positioned in a grid according to their unique num-  ***/
/*** ber (starting with node 0 and increasing by 1 after each pla-  ***/
/*** cement), entirely filling the 3 dimensions in turn (x follow-  ***/
/*** by y, followed by z).                                          ***/
/*** A grid having 'xCPUs'=4, 'yCPUs'=3, and 'zCPUs'=2, thus looks  ***/
/*** as follows ('CN' means 'Compute Node'):                        ***/
/***                                                                ***/
/***    z               ---------------------------------------     ***/
/***   /              /| [CN 12] | [CN 13] | [CN 14] | [CN 15]/|    ***/
/***  /              / |---------|---------|---------|-------/-|    ***/
/*** 0---- x    BACK/->| [CN 16] | [CN 17] | [CN 18] | [CN 19] |    ***/
/*** |             /   |---------|---------|---------|-----/---|    ***/
/*** |            /    | [CN 20] | [CN 21] | [CN 22] | [CN/23] |    ***/
/*** y           /     /---------------------------------/-----/    ***/
/***             ---------------------------------------      /     ***/
/***      TOP ->| [CN  0] | [CN  1] | [CN  2] | [CN  3] |    /      ***/
/***            |---------|---------|---------|---------|   /       ***/
/***            | [CN  4] | [CN  5] | [CN  6] | [CN  7] |<- FRONT   ***/
/***            |---------|---------|---------|---------| /         ***/
/***   BOTTOM ->| [CN  8] | [CN  9] | [CN 10] | [CN 11] |/          ***/
/***             ---------------------------------------            ***/
/***                 ^                             ^                ***/
/***                 |                             |                ***/
/***                LEFT                         RIGHT              ***/
/***                                                                ***/
/*** Given this grid definition it is always possible to determine  ***/
/*** the grid-index of a compute-node for each of the 3 dimensions  ***/
/*** by its unique number. For example: the compute nodes 0, 4, 8,  ***/
/*** 12, 16, and 20, all have a 'gridIndexX' of 0; the nodes 8, 9,  ***/
/*** 10, 11, 20, 21, 22, and 23, all have a 'gridIndexY' of 2; the  ***/
/*** nodes 12-23 all have a 'gridIndexZ' of 1.                      ***/
/***                                                                ***/
/*** [see: PxGridIndexX(), PxGridIndexY(), PxGridIndexZ()]          ***/
/***                                                                ***/
/*** For each node it is also possible to determine its neighbours  ***/
/*** in each of the 3 dimensions.  For example, compute node 5 has  ***/
/*** the following neighbours:                                      ***/
/***  left neighb. = 4  top neighb.   = 1  front neighb.= none\-1   ***/
/***  right neighb.= 6  bottom neighb.= 9  back neigb.  = 17        ***/
/***                                                                ***/
/*** [see: PxMyLeftCPU(), PxMyRightCPU(), PxMyUpCPU(),              ***/
/***       PxMyDownCPU(), PxMyFrontCPU(), PxMyBackCPU() ]           ***/
/***                                                                ***/
/*** Finally, for each node it is possible to determine whether it  ***/
/*** is placed in one of the 'outermost' slices of the grid, i.e.:  ***/
/*** left, right, top, bottom, front, back. CN 23, for example, is  ***/
/*** placed in the rightmost slice,  but also in the slices at the  ***/
/*** bottom and back.                                               ***/
/***                                                                ***/
/*** [see: PxIsLeftCPU(), PxIsRightCPU(), PxIsTopCPU(),             ***/
/***       PxIsBottomCPU(), PxIsFrontCPU(), PxIsBackCPU() ]         ***/
/***                                                                ***/
/*** The logical view of an array is similar to that of the compu-  ***/
/*** te node grid defined above. This means that in the process of  ***/
/*** partitioning  the number of pixels in the x-direction (width)  ***/
/*** of the array is divided by the number of nodes defined in the  ***/
/*** x-direction of the grid. The same holds for the additional y-  ***/
/*** and z-directions.                                              ***/
/*** In the process of partitioning  it may turn out that the size  ***/
/*** of the global array in any of the 3 dimensions  is not a full  ***/
/*** multiple of the number of compute nodes defined in each rela-  ***/
/*** ted dimension respectively. A standard division therefore re-  ***/
/*** sults in the 'mimimal number of pixels in one dimension' that  ***/
/*** all compute nodes are at least responsible for.  Any possible  ***/
/*** amount of remaining pixels in 1 dimension (called 'overflow')  ***/
/*** is partitioned by incrementing (by '1') the 'amount of pixels  ***/
/*** responsible for'  for as many of the lowest numbered nodes in  ***/
/*** that dimension as needed, for all values of the remaining di-  ***/
/*** mensions.                                                      ***/
/***                                                                ***/
/*** [see: PxMinLclWidth(), PxMinLclHeight(), PxMinLclDepth()       ***/
/***       PxOverflowX(), PxOverflowY(), PxOverflowZ() ]            ***/
/***                                                                ***/
/*** An array with 'width'=19, 'height'=10, and 'depth'=7, for the  ***/
/*** grid drawn above will be partitioned in the following manner:  ***/
/***                                                                ***/
/***                ---------------------------------------         ***/
/***              /| (5,4,2) | (5,4,2) | (5,4,2) | (4,4,2)/|        ***/
/***             / |---------|---------|---------|-------/-|        ***/
/***            /  | (5,3,2) | (5,3,2) | (5,3,2) | (4,3,2) |        ***/
/***           /   |---------|---------|---------|-----/---|        ***/
/***          /    | (5,3,2) | (5,3,2) | (5,3,2) | (4,3,2) |        ***/
/***         /     /---------------------------------/-----/        ***/
/***         ---------------------------------------      /         ***/
/***        | (5,4,3) | (5,4,3) | (5,4,3) | (4,4,3) |    /          ***/
/***        |---------|---------|---------|---------|   /           ***/
/***        | (5,3,3) | (5,3,3) | (5,3,3) | (4,3,3) |  /            ***/
/***        |---------|---------|---------|---------| /             ***/
/***        | (5,3,3) | (5,3,3) | (5,3,3) | (4,3,3) |/              ***/
/***         ---------------------------------------                ***/
/***                                                                ***/
/***                 (a,b,c) = (width,height,depth)                 ***/
/***                                                                ***/
/*** Based on this way of partitioning the size of a partial array  ***/
/*** (the part of the entire array one node is responsible for) is  ***/
/*** obtainable from the unique number of the compute node.         ***/
/***                                                                ***/
/*** [see: PxLclWidth(), PxLclHeight(), PxLclDepth() ]              ***/
/***                                                                ***/
/*** Also, it is possible to obtain the index (for each dimension)  ***/
/*** of the starting point of a partial array in the entire array.  ***/
/***                                                                ***/
/*** [see: PxLclStartX(), PxLclStartY(), PxLclStartZ() ]            ***/
/***                                                                ***/
/**********************************************************************/


/*** Global variables *************************************************/

int _fullW;                 /* Global array x-size (core-width)       */
int _fullH;                 /* Global array y-size (core-height)      */
int _fullD;                 /* Global array z-size (core-depth)       */

int _xCPUs;                 /* Nr. of CPUs in x-direction of grid     */
int _yCPUs;                 /* Nr. of CPUs in y-direction of grid     */
int _zCPUs;                 /* Nr. of CPUs in z-direction of grid     */

int _leftCPU;               /* CPU-nr of left neigbour of myCPU       */
int _rightCPU;              /* CPU-nr of right neigbour of myCPU      */
int _upCPU;                 /* CPU-nr of up neighbour of myCPU        */
int _downCPU;               /* CPU-nr of down neigbour of myCPU       */
int _frontCPU;              /* CPU-nr of front neigbour of myCPU      */
int _backCPU;               /* CPU-nr of back neigbour of myCPU       */

/* NOTE: The following parameters represent the minimum number of     */
/* pixels all CPUs are responsible for in each of the 3 directions.   */

int _minLocalW;             /* Min. #elements in x-dir. (on each CPU) */
int _minLocalH;             /* Min. #elements in y-dir. (on each CPU) */
int _minLocalD;             /* Min. #elements in z-dir. (on each CPU) */

/* NOTE: CPUs may be responsible for an additional elemt in any of    */
/* the three directions (due to the fact that the nr. of elemts in    */
/* a certain direction is not a (full) multiple of the nr. of CPUs    */
/* defined in that direction).  The following parameters represent    */
/* the total amount of this 'element-overflow' in each direction.     */

int _overflowX;             /* Element overflow in x-direction        */
int _overflowY;             /* Element overflow in y-direction        */
int _overflowZ;             /* Element overflow in z-direction        */


/*** Functions ********************************************************/


inline int
PxFullWidth()
{
    return _fullW;
}


inline int
PxFullHeight()
{
    return _fullH;
}


inline int
PxFullDepth()
{
    return _fullD;
}


inline int
PxFullSize()
{
    return (_fullW * _fullH * _fullD);
}


/**********************************************************************/


inline int
PxLogPartXcpus()
{
    return _xCPUs;
}


inline int
PxLogPartYcpus()
{
    return _yCPUs;
}


inline int
PxLogPartZcpus()
{
    return _zCPUs;
}


/**********************************************************************/


inline int
PxMyLeftCPU()
{
    return _leftCPU;
}


inline int
PxMyRightCPU()
{
    return _rightCPU;
}


inline int
PxMyUpCPU()
{
    return _upCPU;
}


inline int
PxMyDownCPU()
{
    return _downCPU;
}


inline int
PxMyFrontCPU()
{
    return _frontCPU;
}


inline int
PxMyBackCPU()
{
    return _backCPU;
}


/**********************************************************************/


inline int
PxMinLclWidth()
{
    return _minLocalW;
}


inline int
PxMinLclHeight()
{
    return _minLocalH;
}


inline int
PxMinLclDepth()
{
    return _minLocalD;
}


/**********************************************************************/


inline int
PxOverflowX()
{
    return _overflowX;
}


inline int
PxOverflowY()
{
    return _overflowY;
}


inline int
PxOverflowZ()
{
    return _overflowZ;
}


/**********************************************************************/


inline int
PxGridIndexX(int cpu)
{
    return (cpu % _xCPUs);
}


inline int
PxGridIndexY(int cpu)
{
    return ((cpu / _xCPUs) % _yCPUs);
}


inline int
PxGridIndexZ(int cpu)
{
    return (cpu / (_xCPUs * _yCPUs));
}


/**********************************************************************/


inline int
PxIsLeftCPU(int cpu)
{
    return ((PxGridIndexX(cpu) == 0) ? 1 : 0);
}


inline int
PxIsRightCPU(int cpu)
{
    return ((PxGridIndexX(cpu) == _xCPUs-1) ? 1 : 0);
}


inline int
PxIsTopCPU(int cpu)
{
    return ((PxGridIndexY(cpu) == 0) ? 1 : 0);
}


inline int
PxIsBottomCPU(int cpu)
{
    return ((PxGridIndexY(cpu) == _yCPUs-1) ? 1 : 0);
}


inline int
PxIsFrontCPU(int cpu)
{
    return ((PxGridIndexZ(cpu) == 0) ? 1 : 0);
}


inline int
PxIsBackCPU(int cpu)
{
    return ((PxGridIndexZ(cpu) == _zCPUs-1) ? 1 : 0);
}


/**********************************************************************/


inline int
PxLclWidth(int cpu)
{
    if (PxGridIndexX(cpu) < _overflowX) {
        return (_minLocalW + 1);
    } else {
        return _minLocalW;
    }
}


inline int
PxLclHeight(int cpu)
{
    if (PxGridIndexY(cpu) < _overflowY) {
        return (_minLocalH + 1);
    } else {
        return _minLocalH;
    }
}


inline int
PxLclDepth(int cpu)
{
    if (PxGridIndexZ(cpu) < _overflowZ) {
        return (_minLocalD + 1);
    } else {
        return _minLocalD;
    }
}


inline int
PxLclSize(int cpu)
{
    return (PxLclWidth(cpu) * PxLclHeight(cpu) * PxLclDepth(cpu));
}


/**********************************************************************/


inline int
PxLclStartX(int cpu)
{
    /* Gives index in x-direction of global array representing the
     * start of the partial array for which CPU 'cpu' is responsible.
     */
            
    if (PxGridIndexX(cpu) < _overflowX) {
        return (PxGridIndexX(cpu) * (_minLocalW + 1));
    } else {
        return (PxGridIndexX(cpu) * _minLocalW + _overflowX);
    }
}


inline int
PxLclStartY(int cpu)
{
    /* Gives index in y-direction of global array representing the
     * start of the partial array for which CPU 'cpu' is responsible.
     */
            
    if (PxGridIndexY(cpu) < _overflowY) {
        return (PxGridIndexY(cpu) * (_minLocalH + 1));
    } else {
        return (PxGridIndexY(cpu) * _minLocalH + _overflowY);
    }
}


inline int
PxLclStartZ(int cpu)
{
    /* Gives index in z-direction of global array representing the
     * start of the partial array for which CPU 'cpu' is responsible.
     */
            
    if (PxGridIndexZ(cpu) < _overflowZ) {
        return (PxGridIndexZ(cpu) * (_minLocalD + 1));
    } else {
        return (PxGridIndexZ(cpu) * _minLocalD + _overflowZ);
    }
}


inline int
PxLclStart(int cpu, int bw=0, int bh=0, int bd=0)
{
    /* Gives index in global array representing the start of the
     * partial array for which CPU 'cpu' is responsible - INCLUDING
     * any potential borders surrounding the array structure.
     * 
     * BEWARE: Dependent on array data layout in memory!!!
     */
            
    int     realW = _fullW + 2 * bw;
    int     realH = _fullH + 2 * bh;

    return (((PxLclStartZ(cpu) + bd) * realW * realH) +
            ((PxLclStartY(cpu) + bh) * realW) +
            ((PxLclStartX(cpu) + bw)));
}


/**********************************************************************/


inline void
PxInitPartition(int aw, int ah, int ad,
                int xcpus, int ycpus, int zcpus)
{
    int _myCPU = PxMyCPU();

    _fullW = (aw < 1) ? 1 : aw;
    _fullH = (ah < 1) ? 1 : ah;
    _fullD = (ad < 1) ? 1 : ad;

    _xCPUs = (xcpus < 1) ? 1 : xcpus;
    _yCPUs = (ycpus < 1) ? 1 : ycpus;
    _zCPUs = (zcpus < 1) ? 1 : zcpus;

    _leftCPU  = (PxIsLeftCPU(_myCPU))   ? -1 : _myCPU - 1;
    _rightCPU = (PxIsRightCPU(_myCPU))  ? -1 : _myCPU + 1;
    _upCPU    = (PxIsTopCPU(_myCPU))    ? -1 : _myCPU - _xCPUs;
    _downCPU  = (PxIsBottomCPU(_myCPU)) ? -1 : _myCPU + _xCPUs;
    _frontCPU = (PxIsFrontCPU(_myCPU))  ? -1 : _myCPU - (_xCPUs*_yCPUs);
    _backCPU  = (PxIsBackCPU(_myCPU))   ? -1 : _myCPU + (_xCPUs*_yCPUs);

    _minLocalW = _fullW / _xCPUs;
    _minLocalH = _fullH / _yCPUs;
    _minLocalD = _fullD / _zCPUs;   

    _overflowX = _fullW % _xCPUs;
    _overflowY = _fullH % _yCPUs;
    _overflowZ = _fullD % _zCPUs;
}


inline void
PxRePartition(int xcpus, int ycpus, int zcpus)
{
    PxInitPartition(_fullW, _fullH, _fullD, xcpus, ycpus, zcpus);
}


} // namespace Pattern
} // namespace Array
} // namespace Core
} // namespace Impala

#endif /* __PxPartition_h_*/

---