Dissertation
Dissertation > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory

Research on Accelerating the Requirement Space Exploration Based on the Monotonic Indices Space Method

Author LinZhongWei
Tutor YaoYiPing
School National University of Defense Science and Technology
Course Computer Science and Technology
Keywords Requirement Space Acceleration on Convergence CGM De-centralized Task Pool
CLC TP301.6
Type Master's thesis
Year 2011
Downloads 9
Quotes 0
Download Dissertation

A lot of areas in natural science and social science are involved with the requirement space problem. Exploring the requirement space of the problem is very helpful for solving the requirement fixing problem, performance optimization problem, system performance analysis and evaluation problem and so on. However, along with the increasing system complexity, complex systems always contain high-dimensional models, and the performance measurement function forms in various forms, which make the performance of the existing sequential methods can’t meet the increasing demand of applications. Therefore, developing the research on accelerating the requirement space exploration has important theoretical significance and practical value for promoting the efficiency of exploring the requirement space of high-dimensional and complex problems, reducing the exploration time, and meeting the evolving need of applications.Aiming to the time-consuming disadvantage of the sequential monotonic indices space method in exploring the requirement space of high-dimensional and complex problem, this paper developed research on accelerating the convergence of partition point of hyperbox, parallelizing the sequential monotonic indices space method, and reducing the cost of communication to reduce the solution time. The main work and innovation are as follows:Firstly, a parabola-method-based algorithm ParISearch is proposed for exploring the partition point of monotonic indices space hyperbox. The first step of the monotonic indices space method is to explore the partition point of the given hyperbox. Because of the slow convergence of the dichotomy which is in using now, it can’t meet the demand on timeliness of exploring the requirement space of high-dimensional and complex problems. Therefore, this paper proposed the parabola-method-based algorithm ParISearch to explore the partition point of hyperbox. The algorithm ParISearch imitates the parabola method which is used in Roots of nonlinear equations, and uses three historical points to calculate the next iterative point. According to the experimental results, compared with the dichotomy, ParISearch could reduce the time of exploring by about 25%, promising the demanded accuracy.Secondly, a Coarse-Grained Multicomputer (CGM) model-based algorithm CGMResolve is proposed for hyperbox parallel processing. The monotonic indices space method is highly time and memory-consumed, thus the current sequential execution can’t meet the involving demand on timeliness of exploring the requirement space of high-dimensional and complex problems. In CGMResolve, hyperboxes are considered as fundamental cells for parallel processing, and dispatched to calculative nodes to process. According to the experimental results, the speedup is almost increasing linearly with the number of calculative nodes. For example, we could attain a speedup of 1.658 using 2 calculative nodes, and a speedup of 2.338 using 3 calculative nods.Thirdly, a de-centralized task pool-based algorithm DTPTransfer is proposed for hyperbox storage and migration. In CGMResolve, the hyperbox queue is stored by a global task pool, but the effectiveness turns out low. And we must keep the nodes work-balanced, if using de-centralized task pool. In DTPTranser, a calculative node stores the hyperboxes generated by itself with local task pool, and transfers hyperboxes among the calculative nodes according to the global control mechanism to achieve load balancing. According to the experimental results, the DTPTransfer algorithm reduced the communication time of the total execution time, and promoted the overall processing efficiency: if using 5 calculative nodes, compared with using global task pool, the proportion of communication time decreased by about 50%, and the overall solution time decreased by about 5%.Finally, a LAN-cluster-oriented system for exploring the requirement space is designed and implemented basing on the above work. And then, the requirement space of a simulative air defense system was conducted to test the system comprehensively. According to the test results, compared with the sequential execution with dichotomy, the system could produce high speedup. For example, we could attain a speedup of 2.763 using 2 calculative nodes, and a speedup of 6.027 using 6 calculative nodes.

Related Dissertations
More Dissertations