Page 22 - untitled

Theoretical Computer Science and Parallel Processing
Theoretical Computer Science and Parallel Processing °Applications of graph theory and algorithms severe impact on the performance of these systems.
The focuses of our research include benchmarking
Graphs are used to model many important ap-

Theoretical Computer Science
Theoretical Computer Science plications and are a main tool for solving many the- and fine-tuning for cache/memory performance, dy-
namic load distribution and balancing, optimization
oretical problems. We often start with probing fun- and compilation for interconnection network com-
damental theoretical problems such as the structure munication and parallel I/O. We have constructed
1. Graph theory and algorithms certain rules of competition, are also of interest. In of graphs with certain properties. With these proper- a 32-node dual-CPU PC cluster with a parallel
biological computing we use some important tech- ties, we then design effi cient solutions to them. One Input/Output subsystem and a 12-node dual-CPU
°Tree Root of Graphs: niques, e.g. random sampling, parametric search, example that we work on is the graph augmentation workstation cluster. We also study cluster-based
A tree root of a graph G is a tree T whose k-th geometric cutting, expander graph, matrix search- problem, in which we want to add as few edges as algorithms and integrate these optimizations in the
power for some k > 0 is the graph G exactly. Based ing, etc. to tackle certain subsequence problems in possible to a given graph such that the resulting development of application programs.
on the equivalence of the clique tree (respectively, a given DNA or arbitrary sequence, e.g., fi nding a graph satisfies certain prescribed graph properties.
minimal separator tree) of G and the core of tree maximum density subsequence or a maximum sum This graph augmentation problem has many ap- 3. Grid computing
root when k is even (respectively, odd), we proposed subsequence. We hope to use geometric techniques plications, such as the design of reliable networks, As the data-intensive applications increase
a linear-time algorithm in determining the existence to solve additional problems in biological comput- security of statistical tables and drawing of planar continuously in various domains, scientists nowa- Research Groups
of tree root of a graph, and providing a such tree ing, and moreover, apply them to problems in pat- graphs. We have obtained several fundamental days need to save, retrieve and analyze rapidly
when does exist. tern recognition, image processing, data mining, etc. results for graph connectivity. We are also finding increasing large datasets. A single system has been

difficult to manage such large-scale scientifi c data.
°Maximal Planar Subgraphs: 4. Logic for intelligent agents new properties based on real-life applications. For Built on pervasive Internet standards, grid comput-
example, in Computer Chinese chess, we use graph-
Based on the PC-Tree representation of planar Recently more and more software agents theoretic techniques to efficiently construct large ing enables organizations to share computing and
information resources across department and orga-
graphs, we have developed a (optimal) linear time have been designed to solve real-world problems endgame databases. We use graph theory to model nizational boundaries in a secure, highly efficient
algorithm to find a maximal planar subgraph in an arising from the rapid development of the Internet Chinese chess tie-breaking rules. The problem manner. The Grid provides researchers an integrated

arbitrary graph. This algorithm provides an easily and e-commerce. Some mental attitudes of agents, of finding a consistent algorithm to check for tie- virtual environment to access a wide variety of
Research Groups
understood implementation of PC-Tree that could such as knowledge, belief, intention, commitment, breaking rules has remained open for decades, if distributed resources and to facilitate collaboration
broaden the scope of application for planar graph and trust play very important roles in such systems. not centuries. Another example that we work on is among researchers and organizations. The focuses
algorithms. We formally analyze different aspects of mental the power domination and capacitated domination of our research include data grid system architec-
attitudes from a logical viewpoint and obtain the problem. By transforming power network monitor- ture, high-performance and reliable data access, data
2. Complexity and cryptography: following main results. We propose an epistemic ing rules into a domination problem model, and replication strategy, and parallel scientifi c computa-
An important problem in complexity theory is logic with modalities that represents the trusting adding extra capacity and demand constraints to tion on Grids.
to understand the power of randomness in computa- attitudes and the information transmission action the original graph domination problem, we develop
tion. We show how to remove randomness when between agents, and discuss how an agent's belief is new graph-theoretic techniques to tackle power 4. Language, compiler, and run-time support
systems

space or parallel time is limited in certain ways. We influenced by his trust toward other agents and the monitoring problems, wireless network problems,
show that the question of whether or not random- information he acquires. and other related problems that arise in real world Parallel programming languages, compilers,
ness helps non-deterministic computation is related applications. We make efforts to study variations and run-time support systems are the interfaces
between parallel algorithms and multiprocessor
to the non-determinism versus the determinism 5. Applications of domination problem in special graph classes and systems. We are interested in the essential language
problem and the sequential time versus the space °Applied computation aim to design efficient approximation algorithms features that make parallel machines easy to use,
problem. We also study the problem of constructing with reasonably good approximation ratio. and at the same time we study various compiler and
randomness extractors, which can extract almost Develop a Java-based interactive web ap- run-time support issues that are critical in achieving
perfect randomness from slightly random sources, plication, which supports: communication within high performance. We study the parallelization of
using a short random seed as a catalyst. We provide different interest groups, remote compiling of appli- Parallel Processing sequential codes, the optimization of communi-
Parallel Processing
the first explicit construction of extractors, which cation programs, sharing of an expandable database cation and synchronization, processor-level code
are optimal up to constant factors. Extractors have of computational geometry code, and distributed optimization, parallel data structures and libraries,
We study various topics in parallel processing,
a wide range of applications. We apply them to the displaying of geometric objects. This web applica- including parallel algorithm designs, architectures, and performance evaluation of parallelizing compil-
construction of encryption schemes with everlasting tion has been incorporated into our “Open Compu- compilers, and scientific applications and their ers and compiler-generated codes. We also found
security in the bounded storage model where any tational Problem Solving (OpenCPS)” knowledge implementations. that even in irregular computation, data movement
eavesdropper has only a bounded amount of storage. portal. The integrated web environment facilitates only occurs at processor boundaries. Therefore, we
We also explore the limitation of constructing cryp- algorithmic researchers in geometric computing to 1. Parallel algorithms develop domain decomposition and data reorder-
tographic protocols in the bounded storage model. test their ideas, demonstrate their findings, and teach We have studied various algorithmic problems ing techniques to signifi cantly reduce the amount of

inter-processor data movement.
geometric algorithms in the classroom. related to parallel computing such as task schedul-
3. Geometric computing ing, I/O resource management, I/O scheduling in 5. Practical issues from the implementation

The Voronoi diagram is a very versatile and ° Data confidentiality and personal privacy protection parallel systems, and collective communication of scientific and engineering applications
well-studied geometric construct in geometric on heterogeneous network-based systems. We are We design and implement software libraries

computing. Its properties, complexity and how to Massive amounts of data have been collected also interested in finding good mapping techniques for scientific computations on parallel machines.
compute it are among the fundamental problems to for various purposes. Although sharing the data can to implement serial algorithms in parallel machine We have implemented a tree-code library for the
study. By introducing different metric, such as time- be beneficial to the public, it can also be a threat models. study of astrophysics and multi-fi lament vortex sim-
distance, the diagram will change. In general how to personal privacy. How to facilitate sharing data ulations, a library for parallel sparse matrix compu-
the properties of the Voronoi diagram vary with the while keeping personal privacy intact is the problem 2. High performance cluster computing tations, and novel data structure technology for par-
metric selected and how we make use of the proper- we want to address. We discovered a formal frame- As the recent advances in commodity high- allel unstructured mesh computations. In addition,
ties of the selected metric, if any, to construct the work to discuss privacy leakage, as well as quanti- speed networks and improved microprocessor per- we are also developing parallel simulation methods
diagram is what we plan to study. Other problems tative measures of the severity of privacy leakage. formance, clusters built up from workstations or for numerical wind tunnel simulation and an engine
combustion platform for computing reactive fl ows.

such as Map Labeling, i.e., how to label given fea- We also developed a prototype privacy-enforcing PCs are playing a major role in redefining the con- Key technologies include unstructured mesh gen-
cept of supercomputing. Although clusters of com-
tures of a map so that these labels do not overlap, gateway called CellSecu that can check if sharing a puters can provide enormous computing power at a eration, sparse matrix computation for Euler and
and Defensive Competitive Facility Location, i.e., particular dataset or answering a query violates the relatively low cost, programming for these systems Navier-Stokes PDE solvers, scientifi c visualization,
find the location of a facility so that the gain of privacy policy set by the administrator. is still quite difficult and input/output can have a and parallel implementations using the MPI library.
prospective competitors is minimized according to

12 13