MPI Traffic Program with C++

Goal

I want to solve a traffic problem with MPI.

• We have a road comprised of n points.
• Cars move over these points.
• At each time step, each car may move to the next point.
• A car moves only if the next point is empty.
• The road has periodic boundaries.

Example

“-” is an empty point and “o” is a car:

step = 0: - o o - o - -

step = 1: - o - o - o -

setp = 2: - - o - o - o

step = 3: o - - o - o -

Code

The solution is placed in GitHub.

Dependency

The state of each point at the next time step depends on the current state of itself and its nearest points:

``````P = A point
i = Index of a point
t = Time step
f = A function of

P[i] @(t+1) = f( P[i-1], P[i], P[i+1] ) @t
``````

The function can be divided into two steps:

``````1) if P[i-1] has car & P[i] is empty
P[i] will have the car @t+1
2) if P[i] has car & P[i+1] is empty
P[i] will be empty @t+1
``````

In the first condition `P[i]` needs to be empty, in the second one `P[i]` must have a car. They cannot happen at the same time for a point. Either (1) happens or (2). Therefore, we can separate or reorder them and still we get the same result for ‘P[i] @t+1’ .

Design

Let’s say the road has 12 points, and is modeled by 3 processors. We have 3 `RoadSections` shown below.

Each processor has 4 points plus 2 ghost (G) points. The right ghost point of RoadSection 1 represents point 0 of RoadSection 2 and the left ghost point of RoadSection 1 is an image of point 3 of RoadSection 0.

My approach to the problem can be simply shown in this code:

``````struct RoadSection{

vector<char>& points;

void Run(){
ISendBoundaryPoints();
MoveInternalPoints();
RecvGhosts();
MoveBoundaryPoints();
}

// The rest ...
};
``````

Each `RoadSection` is allocated some `points`. When run is called, each processor run these tasks:

• `ISendBoundaryPoints()`: In a non-blocking way, send boundary points (0,3) to neighboring road sections.
• `MoveInternalPoints()`: Move cars that are not on boundaries (1,2), i.e. defer solving boundaries.
• `RecvGhosts()`: Receive boundary of neighbors which are ghosts in this `RoadSection`.
• `MoveBoundaryPoints()`: A boundary point, now, knows its left and right points, its dependencies, so it can be moved.

Constructor

The rank of a road section and its neighbors are initialized in the constructor

``````RoadSection(vector<char>& _points)
:points(_points)
{
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

leftRank = (rank+size-1)%size;
rightRank = (rank+1)%size;
}
``````

Send Boundary Points

We send the first node of a road section to its left neighbor and the last node to its right neighbor. The send is non-blocking, therefore, these points can be overridden during internal movement, so they are sent via temporary variables.

``````void ISendBoundaryPoints()
{
tmpLeftPoint = points.front();
tmpRightPoint = points.back();
MPI_Isend(&tmpLeftPoint, 1, MPI_CHAR, leftRank, 0, MPI_COMM_WORLD, &leftReq);
MPI_Isend(&tmpRightPoint, 1, MPI_CHAR, rightRank, 0, MPI_COMM_WORLD, &rightReq);
}
``````

Internal Movement

A simple strategy to update points is to use a second array of points as the new position. However, here to save memory the points are updated directionally from left to right and in the original array of points. Point[i] and Point[i+1] are updated at the same time by swap function, we keep a copy of old value of Point[i+1] to be used for updating p[i+2].

``````void MoveInternalPoints(){
char points_i = points[0];
for (size_t i = 0; i < points.size()-1; i++)
{
if (points_i=='t' && points[i+1]!='t' ){
points_i = points[i+1];
swap(points[i], points[i+1]);
}
else{
points_i = points[i+1];
}
}
}
``````

The ghost cells are received from the left and right neighbors. One receive is non-blocking to make sure the second receive is not blocked.

``````void RecvGhosts(){
MPI_Request req;
MPI_Irecv(&rightGhost, 1, MPI_CHAR, rightRank, 0, MPI_COMM_WORLD, &req);
MPI_Recv(&leftGhost, 1, MPI_CHAR, leftRank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Wait(&req , MPI_STATUS_IGNORE);
}
``````

Move Boundary Points

The final step is to move boundary points using their backed-up values and ghost points. Note that Point[0] and Point[last] (=Point[3] in the picture) may have changed during internal movement because of that we use their backed-up value. Moreover, as we explained in the dependency section if boundary points are updated by this method, they certainly didn’t change during internal movement.

``````void MoveBoundaryPoints(){
// This release tmpLeftPoint, tmpRightPoint
MPI_Wait( &rightReq , MPI_STATUS_IGNORE);
MPI_Wait( &leftReq , MPI_STATUS_IGNORE);

if (leftGhost=='t' && tmpLeftPoint!='t'){
swap(leftGhost, tmpLeftPoint);
points.front() = tmpLeftPoint;
}
if (tmpRightPoint=='t' && rightGhost!='t'){
swap(tmpRightPoint, rightGhost);
points.back() = tmpRightPoint;
}
}
``````

Why Vector<char> ?

Each point either has a car or is empty. I needed a boolean type. But, unfortunately, `vector<bool>` is a special case of `vector<>` container where each element is a stored as a bit in contrast with a normal `bool` takes. For more info, read here. Therefore, I used `vector<char>` with `t` and `f` values as true and false to be MPI friendly.

Tags ➡ HPC MPI C++

Subscribe

I notify you of my new posts