Rizal mohd nor, pallav laskar

1.Introduction

Our experiment runs on a commercial SIMD board called the Clearspeed. The Clearspeed board currently has 96 processors and can execute 96 parallel computations simultaneously. Clearspeed supports a parallel programming language tool called the Cn language. Cn is a derivative of ANSI-C and can be used easily to program in the parallel paradigm. Running on a hose computer, the Clearspeed board is capable to handle real-time constraint required to solve problems encountered by Air Traffic Controller

This paper is organized as follows; section 1 of this paper provides an introduction of the air traffic control project paper as well as background and motivation of this project. Section 2 of this paper provides details of the first milestone, the flight trajectory tracking being implemented on project 1. Section 2.1 explains the methods and algorithm used for project 1 and section 2.2 discuss the results being generated. Section 3 of this paper provides details of the second milestone, the flight tracking and radar correlation being implemented on project 2. Section 3.1 explains the methods and algorithm used and section 3.2 discuss on the results being generated. Section 4 of this paper provides details of the third milestone, the collision detection being implemented on project 3. Section 4.1 explains the methods and algorithm used and section 4.2 discuss on the results being generated. Section 5 of this paper provides details of the fourth milestone, the collision avoidance being implemented on project 4. Section 5.1 explains the methods and algorithm used and section 5.2 discuss on the results being generated.

Finally, section 6 provides our contribution in this project to fellow classmates working on the same project, as well as explains some conclusion for our project.

2.Project 1

The second requirement is to create airspace of size 256x256 nautical miles. Planes are given random speeds and random trajectory directions. Project 1 task is to predict the trajectory of each plane based on their speed and location.

2.1.Algorithms used in Project 1

The first part of project 1 is to create a scheduling algorithm. The scheduling algorithm works by running a set number of task every ½ a second. Since the Clearspeed board does not have a real-time clock on it, we have suggested the use of a host application to keep track of the scheduling. The host file, called project.c is a C application that uses timer interrupt to interrupt the hosts to use the CSAPI library to send a semaphore signal to a csx program every ½ a second. This allows us to implement a consistent accurate scheduling on the csx program by handling the interrupt signal being sent from the host. The interaction between the host and the board is minimal. As the signal being sent is negligible in size.

Figure 1 shows the algorithm on the host application that first loads the csx file. It will later run the csx file as if it was run through the standard command line interface. Then it will keep on looping until an interrupt occurs and instruct the code to send a semaphore signal to the clearspeed board. The csx file will then handle the semaphore signal to execute the task that are required to run on the clearspeed board.

The CSX file on the other hand is the part that handles the task to be run on the Clearspeed board. We use the CSAPI function CSAPI function sem_wait(), to wait from an semaphore signal from the host before running the set of task required to be run. The algorithm of this code is shown in Figure 1b: Scheduling algorithm on the clearspeed board.


The second part of project 1 is to create a simulated environment of the airspace being used. For our project we use a 2-D space with a size of 256x256 nautical miles. The range of the airspace is X is +/- 128 nautical miles (nm), and Y range is also +/- 128 nm. Figure 2 is an example of the environment created for this project.

Flights are generated in processors by giving each flight a random starting point in the bounded region defined in figure 3. Figure 3 shows code snippet below gives the part at which the location of each flights are first generated.

128

-128

128

-128


Figure 3. The environment space, where the middle is coordinate (0,0)

The third part of the project is to make the flights move according to the trajectory of the plane. So for every ½ a second, the aircrafts move and if their go out of the boundary of the box, the location is updated by making them flip on the other side of the box. Figure 4, describes the algorithm for having flights re-appear on the other side of the box when it goes out of boundary.

2.2.Results for project 1

To run the application, we have made a make file, to run the application. To run the code, you need to compile it first. Type make and it will automatically compile the necessary files. To see the code in action, all you need to do, is run the executable file called project with the appropriate arguments. Below is an example of running the program.
$ make

$ ./project –i 0

Figure 5 above shows the result of the running program. It shows a snippet of flight 0. The data shows the current location of the plane in the first iteration is at coordinate (x,y)=(1,-7) flying at a height of 3349 feets above the ground. The velocity(dx,dy) is 32(-9.348442,30.604030).

3.Project 2

Project 2 is the second milestone for the ATC project. Its main focus is to develop correlation and location for the plane. The second thing we added in project 2 is to add a random seed number based on current time. This allows us to have a much random output during runtime. Initially, random numbers are given seed based on PE numbers or cycle numbers. We on the other hand have found a way to use current time arguments to seed the values of the random number generators.

3.1.Algorithms used in Project 2

The main idea of our code was to have 3 data set. Data set 0 is (x0,y0), data set 1 is (x1,y1) and data set 1 is (x2,y2). Data set 0, holds the location of the plan, data set 1 holds the current location of the plans. Data set 1, holds the expected trajectory on the next ½ a second, and data set 2 is the generated data for the radar points.


Figure 6 above illustrates how our application works. (x1,y1) gets its next location from the formula above. The radar points on the other hand uses some coefficient generated from a random number from 0 to 1.

After generating the radar points, we then will compare it with other flight tracks. For this, we use swazzle to share the radar point of one plane with other flight tracks. If the radar data matches any other flight tracks, it should then be invalid. Figure 7 shows how swazzle works and how radar data is compared to each other flight tracks.

As you can see in figure 7, first we try to correlate the generated data point for the current plane. If the generated radar data correlates with the current plane, then we mark the radar_match flag. We swazzle around for 96 times, or the number of PEs. The next iteration will get the radar data and flag from the previous PE. It will compare it to its current location and try to do a correlation. If there is a correlation, it will mark the flag accordingly.

Additionally, we have also added a code to seed our random number generator properly. We pass a time argument from the host by using csrun arguments. In figure 8, we show how we do this on the host, and on the csx file.

3.2.Results for project 2

To run the application, we have made a make file, to run the application. To run the code, you need to compile it first. Type make and it will automatically compile the necessary files. To see the code in action, all you need to do, is run the executable file called project with the appropriate arguments. Below is an example of running the program.
$ make

$ ./project –i 0

Figure 5 above shows the result of the running program. It shows all tracks that matches radar=0,1 or 2.

It also shows the beginning seed value used.

4.Project 3

Project 3 is the third milestone for the ATC project. Its main focus is to develop collision detection for the plane. The main idea here is to calculate 20 minutes ahead and find out if there is any collision with any two planes. We have spent a lot of time trying to optimize Batchers’s Algorithm. Particularly, we added our own optimization code on top of Batchers algorithm detect for collision. We call it the quick rejection test, which test to see if a collision is possible between two planes before making the calculations necessary to find out the times for collision.

4.1.Algorithms used in Project 3

Our collision detection works in two steps. Step 1, we use our own quick detection test. The quick rejection test will totally disregard a plane as having a possibility of collision if the plane does not overlap in any two regions. For example, in figure 10, we know that the planes might collide in the x-axis.

Figure 10

However, calculating Tmin and Tmax would be useless unless there is an overlap. So our algorithm test if there is an overlap in the first place. If an overlap occurs, then we will find the necessary Tmin and Tmax value.


In the code above, if there is an overlap between two flight tracks, then we do the second step, which is calculating the intersecting points. To calculate the intersecting points we use the formula below:

Suppose we are given two different points, (x₁, y₁) and (x₂, y₂), and want to find intersecting lines of these two points.

We can do so by setting
A = y₂-y₁
B = x₁-x₂
C = A*x₁+B*y₁
Regardless of how the lines are specified, you should be able to generate two different points along the line, and then generate A, B and C. Now, lets say that you have lines, given by the equations:
A₁x + B₁y = C₁
A₂x + B₂y = C₂
To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.

double det = A₁*B₂ - A₂*B₁

if(det == 0){

//Lines are parallel

}else{

double x = (B₂*C₁ - B₁*C₂)/det

double y = (A₁*C₂ - A₂*C₁)/det

}
Then after finding out the xmin, xmax, ymin,ymax, hmin and hmax, we can eventually get the largest of min values and the smallest of the max value to consider it as a possible collision. This is more popularly known as the Batcher’s algorithm.

4.2.Results for project 3

In figure 13 above, it shows that our code manages to detect collision ahead of time, by 5 minute. We are also able to change the parameter to detect collision 20 minutes ahead of time. If we take one of the output, generated, we are able to plot the points and verify our output. Attached is the output from one of our run, and generated to a graph.

Graph 1, Plot of two flights colliding at xmin=0.199367.

5.Project 4

Project 4 is the fourth milestone for the ATC project. Its main focus is to develop collision avoidance for the plane. Our approach is simple, if two planes are on collision course (determined in Project 3), then potential collision needs to be recorded. Also, the identity of the other plane needs to be recorded. Since we are looking ahead for 20 minutes, the potential conflict may disappear (as one of the planes may be turning and the potential conflict may quickly disappear. For this reason, we will wait for the conflict to reoccur three times before taking action to resolve it. As a result, we need to count the number of times a given conflict is observed and only resolve conflict if after it occurs the third time. When resolving a potential conflict, a trajectory adjustment is considered for just one of the planes. Since in this problem, our planes remain at the same altitude, this adjustment will occur in the flight velocity (direction and/or speed) of one of the planes. For example, the plane could change its flight direction by a 10 degree rotation to the right or left. The location and proposed new course of the plane is sent to all processors and all planes (except the one changing paths) and checked to see if this new path results in any collisions. If a collision still occurs (either with original plane or with another plane), further (or alternate) adjustments are considered and tested. When a collision-free path is found, the pilot of this plane is directed to change his path to the new collision-free path.

5.1.Algorithms used in Project 4

We used a counter variable to count the number of times a conflict is observed. If it occurs three times than we need to do possible adjustment to the trajectory of that flight. But still we need to check if there will be any possible conflict either with original plane or with another plane. If still collision occurs, further adjustments were considered until a collision-free path is found.

In Figure 14, it shows how our conflict detection works. The algorithm works by detecting a collision for a track. If the counter flag, collision_warn=3, then we call the function adjust_flight. The adjusting flight will change the direction of the plan and continue with further conflict detection to be done. This is done recursively, until there are no more collisions.

5.2.Results for project 4

In figure 15 above, we illustrate collision avoidance by showing you part of our output snippet. Our Collision Avoidance algorithm first detects flight 72 is in a collision path with flight 42 and 74 and gives it the first warning. After the next 8 seconds,, flight 74 is no longer in a collision path, but flight 42 remains in the collision path. The 3^rd warning would force flight 74 to adjust its flight path and recheck for future flight collision.

6.Conclusion

Is this ATC project, we have contributed our idea of implementing the interrupt, semaphores and proper use of CSXAPI. We are using swazzle instead of memory copy because of scalability and the speed of transferring data between PE’s is faster. We have optimized Batcher’s algorithm to include a quick rejection test to make computation of collision detection faster.

Directory: ~jbaker
~jbaker -> Updating of an earlier primer by Julia Lee and Dr. Chandra Asthagiri based on Dr. Jerry Potter’s work
~jbaker -> Curriculum vitae johnnie warren baker education summary
~jbaker -> Course Syllabus Parallel and Distributed Computing Fall 2008 Instructor

Download 28.62 Kb.

Share with your friends: