Browsing by Author "He, Jian"

Now showing 1 - 10 of 10
  • Thumbnail Image
    Algorithm XXX: VTDIRECT95: Serial and Parallel Codes for the Global Optimization Algorithm DIRECT
    He, Jian; Watson, Layne T.; Sosonkina, Masha (Department of Computer Science, Virginia Polytechnic Institute & State University, 2007)
    VTDIRECT95 is a Fortran 95 implementation of D.R. Jones' deterministic global optimization algorithm called DIRECT, which is widely used in multidisciplinary engineering design, biological science, and physical science applications. The package includes both a serial code and a data-distributed massively parallel code for different problem scales and optimization (exploration vs. exploitation) goals. Dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel code employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing and scalability. In addition, checkpointing features are integrated into both versions to provide fault tolerance and hot restarts. Important alogrithm modifications and design considerations are discussed regarding data structures, parallel schemes, error handling, and portability. Using several benchmark functions and real-world applications, the software is evaluated on different systems in terms of optimization effectiveness, data structure efficency, parallel performance, and checkpointing overhead. The package organization and usage are also described in detail.
  • Thumbnail Image
    BSML: A Binding Schema Markup Language for Data Interchange in Problem Solving Environments
    Verstak, Alex; Ramakrishnan, Naren; Watson, Layne T.; He, Jian; Shaffer, Clifford A.; Bae, Kyung Kyoon; Jiang, Jing; Tranter, William H.; Rappaport, Theodore S. (Hindawi, 2003-01-01)
    We describe a binding schema markup language (BSML) for describing data interchange between scientific codes. Such a facility is an important constituent of scientific problem solving environments (PSEs). BSML is designed to integrate with a PSE or application composition system that views model specification and execution as a problem of managing semistructured data. The data interchange problem is addressed by three techniques for processing semistructured data: validation, binding, and conversion. We present BSML and describe its application to a PSE for wireless communications system design.
  • Thumbnail Image
    Design and Evaluation of a Data-distributed Massively Parallel Implementation of a Global Optimization Algorithm---DIRECT
    He, Jian (Virginia Tech, 2007-11-15)
    The present work aims at an efficient, portable, and robust design of a data-distributed massively parallel DIRECT, the deterministic global optimization algorithm widely used in multidisciplinary engineering design, biological science, and physical science applications. The original algorithm is modified to adapt to different problem scales and optimization (exploration vs.\ exploitation) goals. Enhanced with a memory reduction technique, dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel scheme employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing and scalability. In addition, checkpointing features are integrated to provide fault tolerance and hot restarts. Important algorithm modifications and design considerations are discussed regarding data structures, parallel schemes, error handling, and portability. Using several benchmark functions and real-world applications, the present work is evaluated in terms of optimization effectiveness, data structure efficiency, memory usage, parallel performance, and checkpointing overhead. Modeling and analysis techniques are used to investigate the design effectiveness and performance sensitivity under various problem structures, parallel schemes, and system settings. Theoretical and experimental results are compared for two parallel clusters with different system scale and network connectivity. An analytical bounding model is constructed to measure the load balancing performance under different schemes. Additionally, linear regression models are used to characterize two major overhead sources---interprocessor communication and processor idleness, and also applied to the isoefficiency functions in scalability analysis. For a variety of high-dimensional problems and large scale systems, the data-distributed massively parallel design has achieved reasonable performance. The results of the performance study provide guidance for efficient problem and scheme configuration. More importantly, the generalized design considerations and analysis techniques are beneficial for transforming many global search algorithms to become effective large scale parallel optimization tools.
  • Thumbnail Image
    Design and Implementation of a Massively Parallel Version of DIRECT
    He, Jian; Verstak, Alex; Watson, Layne T.; Sosonkina, Masha (Department of Computer Science, Virginia Polytechnic Institute & State University, 2006)
    This paper describes several massively parallel implementations for a global search algorithm DIRECT. Two parallel schemes take different approaches to address DIRECT's design challenges imposed by memory requirements and data dependency. Three design aspects in topology, data structures, and task allocation are compared in detail. The goal is to analytically investigate the strengths and weaknesses of these parallel schemes, identify several key sources of inefficiency, and experimentally evaluate a number of improvements in the latest parallel DIRECT implementation. The performance studies demonstrate improved data structure efficiency and load balancing on a 2200 processor cluster.
  • Dynamic Data Structures for a Direct Search Algorithm
    He, Jian; Watson, Layne T.; Ramakrishnan, Naren; Shaffer, Clifford A.; Verstak, Alex; Jiang, Jing; Bae, Kyung; Tranter, William H. (Department of Computer Science, Virginia Polytechnic Institute & State University, 2001)
    The DIRECT (DIviding RECTangles) algorithm of Jones, Perttunen, and Stuckman (1993), a variant of Lipschitzian methods for bound constrained global optimization, has proved effective even in higher dimensions. However, the performance of a DIRECT implementation in real applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice, since it is difficult to predict memory resource requirements in advance. This is especially critical in multidisciplinary engineering design applications, where the DIRECT optimization is just one small component of a much larger computation, and any component failure aborts the entire design process. To make the DIRECT global optimization algorithm efficient and robust on large-scale, multidisciplinary engineering problems, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus of this paper is on design issues of the dynamic data structures, and related memory management strategies. Numerical computing techniques and modifications of Jones’ original DIRECT algorithm in terms of stopping rules and box selection rules are also explored. Performance studies are done for synthetic test problems with multiple local optima. Results for application to a site-specific system simulator for wireless communications systems (S4W) are also presented to demonstrate the effectiveness of the proposed dynamic data structures for an implementation of DIRECT.
  • Thumbnail Image
    Global Optimization of Transmitter Placement for Indoor Wireless Communication Systems
    He, Jian (Virginia Tech, 2002-08-22)
    The DIRECT (DIviding RECTangles) algorithm JONESJOTi, a variant of Lipschitzian methods for bound constrained global optimization, has been applied to the optimal transmitter placement for indoor wireless systems. Power coverage and BER (bit error rate) are considered as two criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. The performance of a DIRECT implementation in such applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice because of unpredictable memory requirements. This is especially critical in S⁴W (Site-Specific System Simulator for Wireless communication systems), where the DIRECT optimization is just one small component connected to a parallel 3D propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations, and surrogate functions for a WCDMA (wideband code division multiple access) simulator are also used to estimate the channel performance. Any component failure of this large computation would abort the entire design process. To make the DIRECT global optimization algorithm efficient and robust, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus is on design issues of the dynamic data structures, related memory management strategies, and application issues of the DIRECT algorithm to the transmitter placement optimization for wireless communication systems. Results for two indoor systems are presented to demonstrate the effectiveness of the present work.
  • Thumbnail Image
    Globally Optimal Transmitter Placement for Indoor Wireless Communication Systems
    He, Jian; Verstak, Alex; Watson, Layne T.; Stinson, C.A.; Ramakrishnan, Naren; Shaffer, Clifford A.; Rappaport, Theodore S.; Anderson, Christopher R.; Bae, Kyung; Jiang, Jing; Tranter, William H. (Department of Computer Science, Virginia Polytechnic Institute & State University, 2002-08-01)
    In this paper, a global optimization technique is applied to solve the optimal transmitter placement problem for indoor wireless systems. An efficient pattern search algorithm ---DIRECT (DIviding RECTangles) of Jones, Perttunen, and Stuckman(1993)---has been connected to a parallel 3D radio propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations. Surrogate functions for a parallel WCDMA (wideband code division multiple access) simulator were used to estimate the system performance for the global optimization algorithm. Power converage and BER(bit error rate) are considered as two different criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. This paper briefly describes the undrelying radio propagation and WCDMA simulations and focuses on the design issues of the optimization loop.
  • Thumbnail Image
    Performance Modeling and Analysis of a Massively Parallel DIRECT— Part 1
    He, Jian; Verstak, Alex; Watson, Layne T.; Sosonkina, Masha (Department of Computer Science, Virginia Polytechnic Institute & State University, 2007)
    Modeling and analysis techniques are used to investigate the performance of a massively parallel version of DIRECT, a global search algorithm widely used in multidisciplinary design optimization applications. Several highdimensional benchmark functions and real world problems are used to test the design effectiveness under various problem structures. Theoretical and experimental results are compared for two parallel clusters with different system scale and network connectivity. The present work aims at studying the performance sensitivity to important parameters for problem configurations, parallel schemes, and system settings. The performance metrics include the memory usage, load balancing, parallel efficiency, and scalability. An analytical bounding model is constructed to measure the load balancing performance under different schemes. Additionally, linear regression models are used to characterize two major overhead sources—interprocessor communication and processor idleness, and also applied to the isoefficiency functions in scalability analysis. For a variety of highdimensional problems and large scale systems, the massively parallel design has achieved reasonable performance. The results of the performance study provide guidance for efficient problem and scheme configuration. More importantly, the generalized design considerations and analysis techniques are beneficial for transforming many global search algorithms to become effective large scale parallel optimization tools.
  • Thumbnail Image
    Performance Modeling and Analysis of a Massively Parallel DIRECT— Part 2
    He, Jian; Verstak, Alex; Sosonkina, Masha; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 2007)
    Modeling and analysis techniques are used to investigate the performance of a massively parallel version of DIRECT, a global search algorithm widely used in multidisciplinary design optimization applications. Several highdimensional benchmark functions and real world problems are used to test the design effectiveness under various problem structures. In this second part of a twopart work, theoretical and experimental results are compared for two parallel clusters with different system scale and network connectivity. The first part studied performance sensitivity to important parameters for problem configurations and parallel schemes, using performance metrics such as memory usage, load balancing, and parallel efficiency. Here linear regression models are used to characterize two major overhead sources—interprocessor communication and processor idleness—and also applied to the isoefficiency functions in scalability analysis. For a variety of highdimensional problems and large scale systems, the massively parallel design has achieved reasonable performance. The results of the performance study provide guidance for efficient problem and scheme configuration. More importantly, the design considerations and analysis techniques generalize to the transformation of other global search algorithms into effective large scale parallel optimization tools.
  • Thumbnail Image
    S4W: Globally Optimized Design of Wireless Communication Systems
    He, Jian; Verstak, Alex; Watson, Layne T.; Stinson, C.A.; Ramakrishnan, Naren; Shaffer, Clifford A.; Rappaport, Theodore S.; Anderson, Christopher R.; Bae, Kyung; Jiang, Jing; Tranter, William H. (Department of Computer Science, Virginia Polytechnic Institute & State University, 2002-07-01)
    In this paper, a global optimization technique is applied to solve the optimal transmitter placement problem for indoor wireless systems. An efficient pattern search algorithm -- DIRECT (DIviding RECTangles) of Jones,Perttunen, and Stuckman(1993)--has been connected to a parallel 3D radio propagation ray tracing modeler running on a 200 node. Beowulf cluster of Linux workstations. Surrogate functions for a parallel WCDMA (wideband code division multiple access) simulator were used to estimate the system performance for the global optimization algorithm. Power coverage and BER (bit error rate) are considered as two different criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. This paper briefly describes the underlying radio propagation and WCDMA simulations and focuses on the design issues of the optimization loop.