Benjamin W Wah - US grants

Researchers at the University of Illinois-Urbana will purchase a hypercube multiprocessor. The equipment will be used for research in computer science, including the following three research projects: (1) Design and implementation of sophisticated computer-aided design tools for VLSI that can run efficiently on the Hypercube multiprocessor. Specifically, tools will be developed for cell placement, wire routing, timing, logic and fault simulation, circuit extraction from mask layouts, and automatic test generation. (2) Intelligent heuristic searches for artificial intelligence applications. Strategies for parallel processing of heuristic searches on the Hypercube will be developed. Also to be considered will be program restructuring for parallel evaluation of logic programs. (3) Performance evaluation of the Hypercube system.

The goal of this research is to develop a multiprocessing system that automatically learns strategies for dynamic decision problems, both in hardware and software, such that the strategy learned is targeted for a multiprocessing system, and that the strategy is the best among those that can be found in the given time and resource constraints of the learning system and the knowledge provided by the users. The class of problems being explored is called dynamic decision problems. These problems may possess one or more of the following properties: the decisions necessary to solve the problem may be interrelated, the decisions are based on dynamic parameters which may be uncertain, the number of possible strategies is very large, and the effects of a decision may not be immediately available after the decision is made. A dynamic decision problem is solved by a combination of domain knowledge and meta-knowledge. Domain knowledge consists of the definition of the problem and its parameters, its representation, and possibly an algorithm (or class of algorithms) to solve it. Meta-level knowledge is knowledge about selecting alternatives to implement in the algorithm and its representation, or finding new ways of solving the given problem. Domain knowledge can be implemented in the form of a program in a computer, for instance, while meta-knowledge is provided by the designers. This research focuses on the development of methods so that some of the meta-knowledge supplied by the designers can be obtained by automatic learning methods. Initially, the focus is on dynamic decision problems for which there are some known solutions, and on learning strategies to solve these problems. The dynamic decision problems addressed include combinatorial search problems and real-time decision problems. The distinguishing features of this research are as follows: First, architectural constraints are being included so that the learning system will find the best strategy given a fixed amount of time and resources, and the computer on which the learning system is implemented. Second, the strategy learned by the learning system also includes consideration of the computer on which it will be implemented. The objectives of this research are to develop methods for automatic learning and to study multiprocessor architectures suitable for learning systems. This area of research is very important and timely. The investigator is well qualified to direct this research. Support is highly recommended.

This proposal is concerned with a workshop on High Performance Computing and Communications (HPCC) for Grand Challenge Applications - Vision, Natural Language and Speech Processing, and Artificial Intelligence. This workshop will bring together 22 invited experts from academia and industry, with the goal of identifying near-term and long term problems in supporting these grand challenge application problems. Many traditional results in these grand challenge applications involving vision, natural language and speech processing, and artificial intelligence were developed without the availability of HPCC systems. On the other hand, computer architects design HPCC systems without considering requirements in vision, natural language and speech processing, and artificial intelligence applications. In this workshop, key issues and potential approaches/research directions for the next five to ten years will be identified, with the goal of answering the following problems: (1) What are grand challenge applications in vision, natural language and speech processing, and artificial intelligence that can be benefited by the availability of HPCC systems? (2) How should HPCC systems be designed so they can support grand challenge applications in these areas? The interdisciplinary HPCC initiative has created a needed for infrastructure development and program planning. The proposed meeting will bring together about 22 experts in the fields with representatives of NSF to discuss current research issues and formulate interdisciplinary research frameworks. The goal of the meeting is to produce a report describing those issues and frameworks which will then be disseminated to the research community.

Wah This research targets efficient distributed computing through intelligent scheduling of application programs. The approach has three components: compiler development, measurement of system loads, and automated learning of optimal scheduling policies. Compilers are modified to extract control and data dependencies from applications programs, emit performance monitoring code, and allow partitioning into processes with predictable resource requirements. A neural network model is being developed to characterize system loads based on ready list lengths, I/O traffic, and network congestion. Finally, an automated learning system will tune scheduling policies to balance system loads using the predicted and measured application program requirements.

Wah This conference, sponsored by the EUROMICRO Association, the IEEE Computer Society, IFIP, AEI, and AICA, focuses on parallel computing, system design methodologies, technology and implementation within the context of application specific computing. Application specific computing is directly related to high performance computing and is a major component in this program. This conference will take place in conjunction with the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems. This grant supports travel by selected graduate students to permit them to attend the conference.

This research will develop formal mathematical conditions for reducing the search space of planning problems, and will demonstrate performance improvements in search engines of planners and other discrete searches. Based on the observation that temporal planning problems can be arranged into stages by time, they can be formulated as dynamic optimization problems with dynamic variables that evolve over time. Due to the presence of general constraints that span across multiple stages, path dominance in dynamic programming cannot be applied to reduce the search complexity. This research will seek new node-dominance conditions in each stage by developing the necessary or necessary-and-sufficient conditions for local optimality and by partitioning the conditions into distributed necessary conditions, based on local constraints in each stage and constraints between adjacent stages. By partitioning the search into stages and by finding only dominating states in each stage using the necessary conditions, the search for feasible or optimal plans can be restricted to a much smaller subspace in each stage, leading to a smaller number of combinations of possible paths that need to be searched across multiple stages.

Three research tasks will be completed in this work. Based on the discrete-space variational search implementing the stopping conditions, research will develop a new planning system that fully supports PDDL2.1 language features, using the constraint-based-interval representation. Temporal flexible scheduling will be extended by formulating a temporal constraint network with flexible time points into a constrained nonlinear optimization problem and by partitioning the search space. Research will study algorithms for partitioning satisfiability (SAT), mixed-integer optimization, and planning problems.

The research is on a new approach that reduces the computational complexity by exploiting the locality of constraints in multi-stage optimization problems. By developing node dominance conditions that identify dominating nodes in each stage, it will lead to reduced search space in each stage and a significant reduction in base of the exponential number of possible paths to be searched across multiple stages. Although a similar approach has been studied in calculus of variations in continuous space, the extension to discrete problems requires the development of a completely new foundation in the theory of Lagrange multipliers in discrete space. The approach developed is general and can be used as stopping conditions in existing planners or integrated into new search algorithms. It can also benefit the solution of other discrete optimization problems, including SAT and mixed-integer optimization.

In addition to training graduate and undergraduate students in their research, the project develops a fundamental approach that will be incorporated into courses on optimization. The results will also carry significant impact on autonomous vehicle planning and will be applied to planners currently developed at the National Aeronautics and Space Administration and Jet Propulsion Laboratory. Improved planners will allow higher dependability of space missions that will benefit society at large.

Title: The Design of VoIP Systems with High Perceptual Conversational Quality
PI: Benjamin W. Wah

Abstract
This research is on the design of real-time two-party and multi-party VoIP (voice-over-IP) systems that can achieve high quality when the interactive conversation is perceived by human listeners. It focuses on the fundamental understanding of conversational quality and its trade-offs in strategies for scheduling the playback of speech frames received, concealing frames lost in the network, routing packets that carry speech frames using an overlay network, and admitting new connections in multi-party conversations. The perceptual quality of a conversation over a network connection depends on the one-way listening-only speech quality and the mouth-to-ear delay incurred from the mouth of a speaker to the ear of a listener. When there are network delays, a conversation perceived by a listener consists of speech segments that are separated by alternating short and long silence periods. This asymmetry leads to low perceptual quality in multi-party VoIP because some speakers appear to be more distant than others, whereas some respond slower than others. In this research, we develop a statistical method to collect subjective test results and a classification method to automatically learn and generalize the results to unseen network and conversational conditions. We study network-control and scheduling algorithms for improving the asymmetry in silence periods and the quality of speech segments received.