Parallel and Distributed Computing

Major: Software Engineering
Code of subject: 7.121.01.E.022
Credits: 5.00
Department: Software
Lecturer: Roman Bazylevych
Semester: 2 семестр
Mode of study: денна
Learning outcomes: РНС1.3. Be able to apply the algorithm and software parallelization methodology in professional activity. РНС1.4. Be able to use optimization methods (linear, non-linear, discrete and other programming kinds) when designing parallel algorithms and software.
Required prior and related subjects: Prerequisites: Software Reliability Theory Corequisites: Master’s Thesis Preparation and Defence
Summary of the subject: Architecture of parallel computers. Basic principles of accelerating computations. Conveyor, vector and matrix systems. Systems with distributed memory and message exchange. Networks for parallel computers. Static and dynamic networks. Topology of networks. Principles of parallelization of calculations. Bernstein's conditions of independence of processes. Detection of parallelism in algorithms. Opportunities and efficiency of parallel computing. Characteristics of parallelization. The size and depth of the computation. A measure of parallelism. Count of data and task dependencies. Speed, efficiency, minimum number of processors. Factors that determine the efficiency of the calculations. Amdagla's law. Principles of designing parallel algorithms. Count dependency problems. Decomposition of algorithms. Clustering tasks. A measure of parallelism. Critical path. Interaction graph of tasks. Scheme of covering tasks by processors. Decomposition of algorithms. Recursive decomposition. Decomposition of input, intermediate and output data. Current, expected and hybrid decomposition. Static and dynamic interaction of subtasks. Coatings. Minimize processors. Static and dynamic coverage. Coverage based on data decomposition, tasks and hybrid. Hierarchical coverage. Parallel application tasks. Parallel sorting algorithms, graphs, search engines and others.
Assessment methods and criteria: Current control: 50% (presentation – 10%, laboratory works – 30% (5 labs 6% each), active participation in discussions on classes 10%) Exam: 50% (written part 40%, spoken part 10%)
Recommended books: 1. H.Jordan, G.Alaghband. Fundamentals of parallel processing. Pearson Education, 2003. 2. Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar. Parallel Computing. Addison Wesley, 2003. 3. Edmund K. Burke Graham Kendall. Search methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. Springer, 2005. 4. Mark Harman. The current state and future of search based software engineering. Future of software engineering (FOSE’07). IEEE, 2007. 5. Christian Blum. Metaheuristic in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, vol. 35. № 3, September 2003, pp. 266 – 306. 6. Search methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. Edited by EDMUND K. BURKE GRAHAM KENDALL. Springer. 2005. 7. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования злектронных устройств. - Львів: Вища школа., 1981. - 168с. 8. Сергиенко Й,В., Каспшицкая М.Ф. Модели й методы решения на ЭВМ комбинаторных задач оптимизации. - Киев: Наукова думка, 1981. - 287с. 9. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. - Киев: Наукова думка, 1986. - 268с.