Project Report
on
Air Traffic Control System
C++ Language and OpenMP
for
Parallel Real Time System Class
By
Rahul Khadse
Files
Project contains following files: -
Header files: -
· "time_functions.h" // Contains all time related functions
· "random_functions.h" // Contains all random number related functions
· "math_functions.h" // Contains all math related functions
Sequential Program Files:-
· “sequential_atc.cpp” // main executable file
· “atc.h” // atc.h (main header file which contains all // functions related to Air Traffic Control System)
· “output.txt” // Contains output in text format for Sequential Program
Single Threaded Sequential Program Files:-
· “single_threaded_atc.cpp” // main executable file
· “output_threads.txt”//Contains output in text format for single threaded program
OpenMP Program Files:-
· “sequential_atc.c” // main executable file
· “atc.h” // atc.h for OpenMP
· “output_openmp.txt” // Contains output in text format for OpenMP Program
Project 1
Project 1 requirement was to create and set up simulation environment for generating and moving traffic.
Requirements
Requirements can be summarized as follows:
1) Set up an environment and Air Space bounded by 256 X 256 Nautical Miles
2) Random Number Generation
3) Initializing all Air Planes with Random starting point, random velocity, random degree of heading direction, and random altitude but within their respective limits
4) Their should be unique Air Craft associated with each P.E
5) Using velocity and direction, path of the Air Plane should be predicted and velocity should be converted to displacements
6) Plane should not leave the airspace and if it reaches the end of the box, it should reenter from other side of Air Space
7) Finally plane should keep on moving forward with same velocity and direction (until it explicitly changed)
I created 3D Airspace (X, Y, Altitude) airspace bounded by box of 256 X 256.
Maximum value of X and Y is 128 while Minimum is -128.
To represent point (x, y), I created following data structure
typedef struct
{
float x;
float y;
}Vector;
To represent Airplanes I created data structure of “AirCraft” as follows :
typedef struct
{
int aircraft_id;
Vector position;
Vector displacement;
float velocity;
float altitude;
float degree_of_direction;
} Aircraft;
In the main file (sequential_atc.cpp), airplanes are represented by AirCraft rr[96] array and pointer to that array AirCraft *ss[96].
“ Vector position” represents current position of Aircraft and is initialized with Random Values. Velocity , altitude and degree_of_direction (which represents heading direction for aircraft) are initialized randomly within their minimum and maximum range.
Once we have velocity and degree of direction, we can calculate the displacement (distance airplane should move in 0.5 seconds). For this I converted velocity into nautical miles and get values using following equation:
// Get Displacement by calculating it using velocity and degree_of_direction
Vector getDisplacement(int velocity,int degree)
{
Vector vec;
vec.x = (velocity * COSINE(degree))/(60*60*60*WAITING_PERIOD);
vec.y = (velocity * SINE(degree))/(60*60*60*WAITING_PERIOD);;
return vec;
}
Also
int reachedBoundary(Aircraft *rr);
function that checks whether the given aircraft has left the Airspace and returns 1 if it has else it returns 0;
void enterAgain(Aircraft *rr);
function checks if Aircraft has left boundary and reenters it by flipping the signs of coordinate. It also takes care if reentry point of aircraft is within the bound or not.
void add_dxdy(Aircraft *rr) and void Update_Positions(Aircraft *rr[96],float sec)
makes possible to continually add the displacement values in the Aircraft and keep them moving.
Update_Position add amount of displacement to aircraft according to time passed. “float sec”
Random Functions:
Generating Random Number is prime requirement for this project. I created following function to achieve this. Function calculates Random Number with help of Poisson’s Distribution and evenly distributes Random across given range.
Furthermore if we use only rand () function to calculate Random number, it will not distribute the results across min and max range and it would give almost same Random Number when called by several threads at the same time.
But following function works fine even if several threads call it at the same time.
int Generate_Random_within_Range (unsigned int min, unsigned int max)
{
int base_random = rand(); /* in [0, RAND_MAX] */
if (RAND_MAX == base_random) return Generate_Random_within_Range(min, max);
/* now guaranteed to be in [0, RAND_MAX) */
int range = max - min,
remainder = RAND_MAX % range,
bucket = RAND_MAX / range;
/* There are range buckets, plus one smaller interval
within remainder of RAND_MAX */
if (base_random < RAND_MAX - remainder) {
return min + base_random/bucket;
} else {
return Generate_Random_within_Range (min, max);
}
}
Math Functions:
Math functions are inbuilt in C++. But inbuilt sin and cos function was not working in some special cases.
When sin = degree + 90{90,270,450…….}; instead of giving value as zero, it was return some garbage value.
Also when I tried to find cos of 180, but it was giving me some large garbage value. Hence I decided to make my own customized SINE and COSINE functions, which would be flaw free.
I can pass the value in Degree, instead of radians into it to get results in my customized SINE and COSINE functions.
“math_functions.h” contains the Mathematical Function Required for Project.
Likewise I customized all Mathematical functions to eliminate any weird results. Such as:
1) SINE and COSINE
2) Degree and Radian Conversions
3) Minimum, Maximum, and Absolute Functions
4) Some other Math functions
Time Functions:
“time_functions.h” contains time related functions.
It contains
1) Wait_for_Number_of_Seconds(seconds): functions which provides us waiting time of number of seconds provided.
2) fiveSecondWait()
3) float resetime() and float gettime(float) :
resetime() returns the current clock cycle which we can save to some float variable say “InitialTime”. When we pass this variable “InitialTime” to “gettime”; it returns us the amount of time since the “resettime” has been called. In this way we can have multiple time trackers in the program. I have used this functions to keep track of time for update, radar and correlation ; Conflict Detection and Avoidance . With the help of these function ,
Radar and Correlation happens every 0.5 seconds, Conflict_detection and Avoidance happens every 8.0 seconds and Position of Aircraft is updated every 0.5 seconds.
Refer to following code:
do {
// Do Radar_And_Correlation every 0.5 seconds
if (getTime(Init_Radar_Time)>0.5) {
Radar_And_Correlation(ss);
Init_Radar_Time = resetTime();
}
//Do Conflict_Detection_And_Avoidance every 8.0 seconds
if (getTime(Init_Conflict_Time)>8.0) {
Conflict_Detection_And_Avoidance(ss);
Init_Conflict_Time = resetTime();
}
// Update Position of AirCraft every 0.5 seconds
if (getTime(Init_Update_Time)>0.5) {
Update_Positions(ss,0.5);
Init_Update_Time = resetTime();
}
} while (getTime(InitialTime)<24.0);
Algorithm followed for Project 1:
1) Initialize the required data structures and variables
2) Initialize all AirPlanes with random values and id
3) Add appropriate displacement using velocity and direction
4) Update Position after t seconds and
5) Reenter the Airplane if it is crossing Airspace borders
6) Repeat steps 3), 4) and 5) for several times
7) End
Project 2
Project 2 is an extension of Project 1 and uses project 1 for initial environment.
Requirements
Requirements can be summarized as follows:
1) Set up environment and initialize it using Project 1
2) Add altitude component which should be between 3000 to 6000 feet
3) Simulate the noise in Airplane by adding random noise component to their positions
4) Track and Correlate those noise value to predicted ones
5) Generate the Radar and move it to mono memory and update the position of those Airplanes
Algorithm and Functionality
1) Initialize the required data structures and variables
2) Initialize all AirPlanes with random values and id
3) Add appropriate displacement using velocity and direction
4) Update Position after t seconds and
5) Reenter the Airplane if it is crossing Airspace borders
6) Add Random Component to original positions and generate the Radar. Check whether if current radar matching with position. If not check with other radars in to the loop and update the positions.
7) Repeat steps 6) for every Airplane 0 to 95
8) If number of radar found for Airplane is equal to 1 , then update the position of Aircraft with new Radar value. Otherwise display “No Radar Found ”
9) End
Project 3
Requirements
Project 3 is an extension of Project 2 and uses project 2 for initial environment and Radar Generation. It focuses on task of Conflict Detection. Conflict Detection is performed using Batcher’s Algorithm to determine if any two aircrafts are on a collision course. Two aircraft within 3 nautical miles or 2000 feet are considered to be in collision.
Values of all constrains are customizable and can be changed by editing in their definition.
#define TOLERANCE_FOR_CONFLICT 3.0
// Two planes can be in conflict or collision if they are only TOLERANCE_FOR_CONFLICT distance apart
#define TOLERANCE_FOR_ALTITUDE 2000.0
// Two planes can be in conflict or collision if they are within TOLERANCE_FOR_ALTITUDE altitude
#define TIME_AHEAD 20.0// Two planes are checked for TIME_AHEAD minutes for Conflict
Algorithm Flow
Conflict detection is handled by the function by following functions : -
1) In_conflict (when passing Aircraft by reference)
2) Has_Conflcit(when passing Aircraft by value)
The two intersection points are calculated for each axis and stored in min_x,min_y,max_x and max_y.
Furthermore Biggest Min and Smallest min calculated and stored in “time_min” and “time_max”.
Also altitudes of both Aircrafts are checked if they are within 2000 feet of each to other.
After this the values of time_min (biggest min) and time_max(smallest max) are checked.
If biggest min time on all dimensions is smaller than smallest max time and times are in the range of 20 minutes, then two aircrafts are in Conflict.
Function “Conflict_Detection_And_Avoidance” checks whether there is conflict across all Airplanes. It loops for 95/2 times. In this way one half of Airplanes can be checked for the Conflicts with other half of Airplanes and we can resolve those conflicts using next Project 4 : Collision Avoidance.
Project 4
Requirements
After Collision Detection we need to alter the path of Aircraft if they are in Potential Conflict. We can avoid conflict after detection and which is only requirement of Project 4 : Collision Avoidance.
Functionality
My project uses same function as of Project 3 to detect potential Conflicts.
1) Function “Conflict_Detection_And_Avoidance” try to check if there are any conflicts between all aircrafts .
(two aircrafts at the time using Has_Detection or In_Conflict(Aircraft *plane1,Aircraft *plane2) functions. )
2) Function keep on counting no of conflicts between two aircrafts. If there are more than 3 conflicts then it looks forward to call “Conflict_Avoidance” function
3) “Conflict_Avoidance” function first tries to avoid by changing direction for five times. If conflict is yet not resolved; then function tries to resolve it by changing Altitude for five times. If conflict can not be resolved by altering Altitude or Direction, then it changes the velocity of Aircraft to avoid the Conflict or Collision.
4) Function “ChangeDirection” for Changing the Direction for two Aircrafts: it changes 5 degree at the time ;
Function “ChangeVelocity” for Changing the Velocity for two Aircrafts: it changes velocity by 100 nautical miles per hour at the time;
Function “ChangeAltitude” for changing the Altitude for two Aircrafts by 2000 feets
5) Whole loop repeats 95/2 times to avoid conflicts for all Aircrafts
Main Function ()
In main function, we create a Aircraft Array and Pointer values to it. Also timestamps for Update and Radar operations are calculated and stored in the variables (by using get_cycles).
Aircraft are initialized randomly and referenced to Aircraft is given to their respective pointers.
Programs loops through 16 minor cycles of 8 seconds each (that means 128(=16 * 8) times) and carry along update operation, Radar Operation every 0.5 seconds and Conflict Detection every 8 seconds. (For Sequential Program)
Single Threaded Sequential Program
When I tried to calculate speedup of OpenMP program vs Sequential Program, speedup was floating around 1 and both OpenMP program and Sequential Program has more or less same running times. After some research, I figured out that my Sequential Program was running on multiple cores at the same time even though it is sequential. Hence in order to force sequential program to run on single core, I rewrote the sequential program such that it would only use single thread to run. Refer “single_threaded_atc.cpp”
I used <pthread.h> library (POSIX) to implement this.
OpenMP Program
To achieve parallelism, I developed OpenMP program by using openmp functionalities including
#pragma omp parallel num_threads(NUM)
#pragma omp barrier
#pragma omp flush
#pragma omp for
across the whole program.
Following function has been parallelized to pick parallelism using OpenMP.
// Initializes all AirCrafts with Random Values
void Initialize_ATC(Aircraft rr[96], Aircraft *ss[96])
// Creates Radar(Randomly) in each Airplane
void Radar_And_Correlation(Aircraft *air[96])
{
// Update Position of all Planes after t seconds
void Update_Positions(Aircraft *air[96],float t)
// Detects the conflict across all planes and avoids it
void Conflict_Detection_And_Avoidance(Aircraft *air[96])
In each function, to prevent any conflict between threads (contention for memory or variable), I used following method. For each loop in the function which is to be parallelized ,
int nthreads = omp_get_num_threads();
int ID=0;
ID = omp_get_thread_num();
for(i=ID;i<NO_OF_PES;i+=nthreads)
Hence if we have four threads,
Thread 0 will execute iteration number 0,4,8,12,…..and so on.
Thread 1 will execute iteration number 1,5,9,13,…..and so on.
Thread 2 will execute iteration number 2,6,10,14,…..and so on.
Thread 3 will execute iteration number 3,7,11,15,…..and so on.
Speedup
Speedup is calculated as follows:
Speedup = Sequential Program Execution TimeParallel Program Execution Time
I calculated speedup using Single Threaded Sequential Program (to obtain true sequential time) vs Parallel Program (OpenMP) Execution Time.
Both programs have a loop in which there is one update, one radar and one conflict detection and avoidance operation. Following charts shows results obtained when no of operations are increased by increasing iteration count. Speedup is calculated for each loop and average is taken at the end.