Below is the file 'aca319/lab9.txt' from this revision. You can also download the file.

ACA 319
Laboratory Report: Lab 9.

1. Implementation of algorithms and results observed.

The program has two key objectives:
  1. represent each car with a distinct PE and ensure that 
     cars respond to each other as specified. cars should 
     obey the road rules and not overtake each other!
  2. output the state of the track after each iteration.

Objective (1)

Each car makes a decision as to whether it should accelerate 
or brake based on the position of the next car on the track. 
As the track is one-lane and circular, the next car will never 
change.

This decision making process implies a data dependency. Each 
car on the track is data-dependent on the next car on the track.

The solution I have used for this data-dependency is for each 
processor to call MPI_Sendrecv() at the completion of each 
iteration. The call sends the processor element's car's position 
to the car behind it, and receives the position of the car in 
front.

Objective (2)

Each iteration we wish to display the track and the position 
of each car upon it. Clearly the data-dependency here is that 
a single processor element (which does the output) must know 
the position of all cars on the track.

This has been achieved without a dedicated processor to provide 
output. After each processor has updated the position of its 
car (n is the number of nodes);
  * the first processor receives a message from each of the 
    (n-1) other nodes indicating the position of that car.
    when it has received all the messages, it displays the 
    track.
  * all other processors use MPI_Send() to transmit their 
    position to the first processor.

My implementation is attached as "lab9q1.c". There are several 
constants at the top of the source file which can be modified 
to vary the size of the track, and the speed at which cars 
accelerate and decelerate.

Results observed:

Each line represents the track - as the track is circular, the start 
and end border each other.

For a small number of cars on the track, output such as this occurs; 
(5 cars on a 50 unit long track)

----------0-----------1-----------2-----------3---

--------3------------0-----------1-----------2----

------2-------------3-----------0-----------1-----

----1--------------2-----------3-----------0------

--0---------------1-----------2-----------3-------

3----------------0-----------1-----------2--------

----------------3-----------0-----------1-------2-

--------------2------------3-----------0-------1--

In general there is sufficient space that the cars can accelerate 
and decelerate according to the rules, without any jamming 
occuring. Cars are not overtaking each other in this output, 
and the other rules appear to be taking effect (acceleration 
and deceleration can be observed.)

With the same track (50 units long) and 15 cars this 
output is produced:

0--1--2--3--4--5--6--7--8--9--A--B--C--D--E-------

0--1--2--3--4--5--6--7--8--9--A--B--C--D--------E-

0--1--2--3--4--5--6--7--8--9--A--B--C----------DE-

0--1--2--3--4--5--6--7--8--9--A--B------------CDE-

0--1--2--3--4--5--6--7--8--9--A------------B--CDE-

0--1--2--3--4--5--6--7--8--9------------A----BCDE-

0--1--2--3--4--5--6--7--8------------9------ABCDE-

0--1--2--3--4--5--6--7------------8--------9ABCDE-

0--1--2--3--4--5--6------------7----------89ABCDE-

0--1--2--3--4--5------------6------------789ABCDE-

0--1--2--3--4------------5--------------6789ABCDE-

0--1--2--3------------4----------------56789ABCDE-

0--1--2------------3------------------456789ABCDE-

Traffic jamming is occuring! The explanation is simple;
  * in the first iteration, "E" has enough room to move 
    so it accelerates. Nodes "0" through "D" are too 
    close to the next car so they do not move in this 
    iteration.
  * in the next iteration, the same applies; E 
    decelerates to avoid hitting "0". "D" moves into 
    the newly created clear space. All other nodes 
    are too close to each other and do not move.
  * the cycle repeats. Nodes bunch together so tightly 
    through coincidence; this behaviour does change as the 
    track size is varied. However, with a sufficient 
    number of cars a moving traffic jam is observed as 
    in this case.