Lopez Sanchez, Efraim Josue (2014) Automatic Generation of Real-Time Aircraft Simulation System Configurations. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
1MBLopezSanchez_MASc_F2014.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
Building configurations for real-time aircraft simulation systems is a challenging task. It involves the distribution of the applications among different scheduling processes, bound to different CPU's, in such a way that the applications' priority and expected execution order are taken into account.
In this thesis, we report on a study conducted at CAE Inc., a world leading manufacturer of flight simulation products, in which we have developed an approach to automatically build configurations. Our approach is based on a greedy algorithm that uses heuristics to distribute many applications into different partitions in such a way that inter-partition communication is minimized, the load across partitions is balanced, and each partition is denoted as a binary tree (the data structure used by the scheduler to run the applications). The configuration is also constrained by the priority and execution time of the applications.
When applied to CAE, our approach produces configurations that in most cases outperform or are similar to those generated by a domain expert.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Electrical and Computer Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Lopez Sanchez, Efraim Josue |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Electrical and Computer Engineering |
| Date: | 20 May 2014 |
| Thesis Supervisor(s): | Hamou-Lhadj, Abdelwahab |
| ID Code: | 978650 |
| Deposited By: | EFRAIM JOSUE LOPEZ SANCHEZ |
| Deposited On: | 03 Nov 2014 14:40 |
| Last Modified: | 18 Jan 2018 17:47 |
References:
1. Karypis, G. and Kumar, V., (1998), “Multilevel algorithms for Multi-Constraint Graph Partitioning,” In proc. of the 1998 ACM/IEEE Conference on Supercomputing, Orlando, FL, USA.2. Karypis, G. and Kumar, V., (1995), “METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0,” Technical Report, Department of Computer Science, University of Minnesota. Minnesota, USA.
3. Schloegel, K., Karypis, G. and Kumar, V., (2002), “Parallel static and dynamic multi-constraint graph partitioning," Concurrency and Computation: Practice and Experience, 2012, 14(3), pp. 219-240.
4. Hagen, L. and Kahng, A.B, (1992), “New spectral methods for ratio cut partitioning and clustering,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(9), pp. 1074-1085.
5. Federal Aviation Administration, (2006), “Part-60 Flight Simulation Training Device Initial and Continuing Qualification and Use,” Federal Aviation Administration, National Simulator Program, Federal Register, 71(209), October 30, 2006. Washington, USA.
6. Kernighan, B.W. and Lin, S., (1970), “An Efficient Heuristic Procedure for Partitioning Graphs”, In the Bell System Technical Journal, 49 (1970), pp. 291-307.
7. Jain, Anil K., (2010), “Data Clustering: 50 Years Beyond K-means”, In Pattern Recognition Letters 31 (award winning papers from the 19th International Conference on Pattern Recognition, Tampa, FL, USA), 31(8), 1 June 2010, pp. 651-666.
8. Karger, D.R., (1993), “Global min-cuts in RNC, and other ramifications of a simple min-out algorithm,” In proc. of the fourth annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 21-30.
9. Luxburg, Ulrike von, (2007), “A tutorial on spectral clustering,” Statistics and Computing, December 2007, 17(4), pp. 395-416.
10. Wei, Y.-C. and Cheng, C.-K., (1989), “Towards efficient hierarchical designs by ratio cut partitioning,” In proc. of the 1989 IEEE International Conference on Computer-Aided Design, Santa Clara, CA, USA, pp. 298-301.
11. Yeh, C.-W., Cheng, C.-K. and Lin, T.-T.Y., (1992), “A probabilistic multicommodity-flow solution to circuit clustering problems,” In proc. of the 1992 IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, USA, pp. 428-431.
12. Chan, P.K., Schlag, M. and Zien, J., (1992), “Spectral K-Way Ratio-Cut Partitioning Part I: Preliminary Results,” Technical Report, Computer Engineering Board of Studies, University of California, Santa Cruz, CA, USA.
13. Shi, J. and Malik, J., (2000), “Normalized Cuts and Image Segmentation,” In IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), pp. 888-905.
14. Abramowitz, M. and Stegun, I. A., (1972.), "Stirling Numbers of the Second Kind," §24.1.4 In Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 824-825.
15. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., (2009), “Breadth-first search” §22.2 In Introduction to Algorithms, third edition, The MIT Press, pp. 594-602.
16. Maini, H., Mehrotra, K., Mohan, C. and Ranka, S., (1994), “Genetic Algorithms for graph partitioning and incremental graph partitioning,” In proc. of the 1994 ACM/IEEE Conference on Supercomputing, Washington, DC, USA, pp. 449-457.
Repository Staff Only: item control page
Download Statistics
Download Statistics