Jeanne Ferrante - US grants

To achieve maximum benefit from tiling, compiler optimization must exercise more control over data movement and storage assignments than is commonly done. Hierarchical tiling takes responsibility for several phases of compilation and code improvements that are traditionally done separately, such as scalar replacement, register allocation, generating message passing calls, and storage mapping. It uses the mechanisms of explicitly naming and copying data to control the movement of data up and down the memory hierarchy and to exploit all levels of parallelism. Its effectiveness as a systematic framework for hand-crafting highly optimized code has been tested on scientific applications for IBM SP1 system. This project will extend the research in compiler optimizations by investigating the following: (1) Develop a parameterized machine model that captures the architectural information needed to guide hierarchical tiling. (2) Study interactions between tiling at various levels of granularity. (3) Incorporate hierarchical tiling into the SUIF toolset. (4) Extend the work to disk storage, explicit I/O and implicit paging virtual memories. (5) Validate the approach using various programs on different parallel machines.

EIA-98-02219
Joseph Pasquale
University of California, San Diego

CISE Research Infrastructure: The UCSD Active Web

UCSD is investigating system and application support issues for a next-generation World Wide Web, called the "Active Web." The Active Web is premised on the support for active content, content that is rich in multimedia and references to other objects, and for mobile agents, programs that can move about and execute on remote servers, carrying out requests at a distance on behalf of clients. These servers are no longer passive databases as in today's Web, but context-sensitive knowledge networks that contain all kinds of active content. Between the servers, there is a constant exchange of agents, which add to, refine, form interconnections, and make consistent, the distributed content. In the Active Web, there is a high degree of resource sharing, usage is bought and sold as in a market economy, and security is paramount. This grant will allow UCSD to purchase large-scale computer and storage servers and a high-speed network that will connect the various laboratories, and will form a small-scale Active Web prototype.

The project is taking a department-wide coordinated approach, integrating the research efforts in systems, security, multimedia, content-based search, scientific metacomputing, and, tools for software/hardware design and analysis.

Tiling is a well-known optimization technique that has been used to obtain orders of magnitude performance improvements on certain types of computer programs -- ones with nicely structured loops and regular memory accesses. This research will extend tiling and related optimization techniques to a larger class of programs. The methods employed to carry out these goals are: (1) Collect a corpus of scientific applications, including unstructured programs and programs with irregular memory accesses. (2) Build a high- level analysis tool to study this corpus and to provide information that can be used to guide program transformations. (3) Develop more powerful transformations to extend tiling to this corpus. These transformations will be embodied in a source-to- source program restructurer. (4) Build an architecturally-driven guidance system to guide the choice of transformations. This system will model the multitiered parallelism and memory hierarchies of modern computers. (5) Evaluate the new transformations compared to hand-optimized versions of the applications. The projected impact of the work is the development of compiler technology that will automatically improve the performance of a broad class of computer programs for scientific applications.

Predicated execution is a feature used in the Explicitly Parallel
Instruction Computing (EPIC) architecture for achieving the
instruction level parallelism (ILP) needed to keep increasing future
processor performance. The IA-64 processor being developed at Intel
with Hewlett Packard is an example of an EPIC architecture. An
advantage of predicated execution is the elimination of
hard-to-predict branches by combining both paths of a branch into a
single path, thereby obtaining additional opportunities for ILP.
However, this merging of several paths into one has disadvantages, as
it complicates optimizations and scheduling in both software and
hardware.

This research develops a comprehensive framework for new compiler and
hardware analysis whose projected impact is to realize the performance
of predicated execution. Underlying our framework is the efficient
maintenance and use of predicate relationships and precise information
about predicated regions. This proposal builds on our prior work by
(1) incorporating critical path and resource constraints into a
compiler intermediate form for predicated compilation, (2) developing
hardware structures to allow predicate speculation and out-of-order
execution, (3) developing software and hardware dynamic predication
and (4) developing predicate-sensitive compiler optimizations,
especially those based on value prediction or profiling.

Advances in network and middleware technologies have brought computing with many widely-distributed and heterogeneous resources to the forefront, both in the context of Grid Computing and of Internet Computing. These large distributed platforms allow scientists to solve problems at an unprecedented scale and/or at greatly reduced cost. The high level goal of this work is to further the development of software methodologies and algorithms to enable scientists,
engineers and others to use large heterogeneous distributed systems.

Application domains that can readily benefit from such platforms are many; they include computational neuroscience, factoring large numbers, genomics, volume rendering, protein docking, or even searching for extra-terrestrial life. Indeed, those applications are characterized by large numbers of independent tasks, which makes it possible to deploy them on distributed platforms with high network latencies. More specifically, in this work we assume that all application data initially resides in a single repository, and that the time required to transfer that data is a significant factor. Efficiently managing the resulting computation is a difficult and challenging problem, given the heterogeneous and typically dynamic attributes of the underlying components. Such an approach allows for adaptivity and scalability, since decisions and changes can be made locally.
This approach is particularly effective for scheduling in environments that are heterogenous, dynamic, and unstructured, such as global and peer-to-peer computing platforms consisting mostly of home PC's.

This research develops a simple yet general computation and communication model for Grid and Internet platforms, and autonomous and decentralized scheduling techniques based on this model. It analyzes the optimality of these techniques in terms of steady-state and overall application performance. Further, it encorporates adaptability and fault-tolerance, and evaluates the resulting techniques by both simulating and running real applications on actual testbeds. Its overall impact to the scientific community is to enable scientists to solve important classes of problems faster and in a more cost-effective fashion.

0314180
Ferrante

Scheduling computational tasks on a given set of processors is a key issue for high-performance computing. Future computing systems, such as the computational grid, are likely to be widely distributed and strongly heterogeneous. This three-year US-France cooperative research award between the University of California at San Diego, Ecole Normal Superieure and French National Institute for Research in Informatics and Applied Mathematics (INRIA) in Lyon addresses the impact of heterogeneity on design and analysis of static scheduling techniques on grid-based systems. The project has three major objectives: (1) development of hierarchical, steady state scheduling algorithms for heterogeneous platforms; (2) adaptation of peer-to-peer strategies for client-server applications; and (3) extension of SIMGRID simulation methodologies and tools. SIMGRID is a discrete-event simulation toolkit that can be used for distributed applications and computing environment topologies. The researchers involved in this project are: Jeanne Ferrante, Larry Carter and Henri Casanova of the University of California at San Diego and the San Diego Supercomputing Center, and Eddy Caron, Yves Robert of the Ecole Normale Superieure in Lyon, Frederic Vivien of INRIA.

This award represents the US side of a joint proposal to NSF and INRIA. NSF provides funds for visits to France by US investigators and students. They will participate in joint research and a concluding workshop at the end of the third year. INRIA supports the visits of French researchers to the United States. The joint activities take advantage of combined US-French expertise in models and algorithm techniques for scheduling on large-scale distributed, grid-based systems. The project advances NSF's priority area - cyberinfrastructure research and development - which will enable collaboration among scientists and engineers across disciplines and national boundaries.

This grant is directed towards planning the new curriculum which will produce more computer engineering graduates who are better prepared for the rapidly changing and diverse world of industry. A key component of this new curriculum will be the incorporation of service learning and multidisciplinary teamwork. This is part of a larger effort at UC San Diego for incorporating multidisciplinary teamwork and service learning, undergraduate research, communication skills, and intervention to realize student potential into the engineering curriculum at the Jacobs School of Engineering at UC San Diego. They are building on UCSD-TIES a service learning activity, initiated with the National EPICS program at Purdue University. The program offers undergraduates an opportunity to be part of a multidisciplinary team that provides technical expertise to non-profit community organizations. Students are being guided by faculty, community organizations, graduate students and each other in their quest to provide engineered products and services unavailable to organizations in need. The program goals are to provide skills in teamwork, leadership, technical prowess, organization, discipline, cooperation, communications, and motivation to students through the application of engineering principles to real-life problems and opportunities.

It will also produce a model program which could be easily replicated for similar benefits at other institutions. The proposed interventions would also improve performance and success of their more diverse population.

A three-year partnership of the UCSD Jacobs School of Engineering and the San Diego Supercomputer Center focuses on getting approximately 22,000 sixth- through ninth-grade students and 360 teachers involved in using information technology through gaming in order to solve complex problems related to STEM content. It provides summer experiences for girls through established area summer camps such as TechTreck and Sally Ride Science and in-service on the related content and activities for San Diego area teachers so the project can influence all the students of those teachers. A greater, but less intense impact on students is through encountering the game on the web. The game will be a problem-solving game bringing the students as avatars in contact with environmental problems they must solve. The solutions will require using virtual tools that have been used in the classroom and involve consulting with scientists.

Scholarships are being awarded to full-time students majoring in engineering or computer science who demonstrate both academic potential and financial need. Twenty qualifying freshmen students are receiving $3,000 annually for four years and forty upperclassmen are reciving $3510 annually for two years. Special emphasis is being placed on recruiting members of groups underrepresented in engineering and computer science. The scholars are engaged in collaborative learning experiences, have access to tutoring, and receive mentoring and individualized advisement. The opportunity to engage in faculty supervised research is also available to the scholars.

Synthetic biology is an emerging field lying at the interface of engineering, science and mathematics. It is concerned with the design, construction and analysis of novel biological systems, with the ultimate goal of enabling beneficial applications in health, materials and energy. One approach to synthetic biology begins with understanding basic components and systematically increasing complexity, one step at a time, first understanding simpler networks before integrating that knowledge into understanding the functioning of more complex ones. A key element of this approach is the development of mathematical models that can be used in analysing and predicting the dynamic behavior of fundamental components, as well as in understanding how components interact when combined in a more complex system.

The PI, Dr. Ruth Williams, a Professor in the Mathematics Department at the University of California, San Diego, has extensive experience with mathematical analysis and control of complex stochastic network models arising in non-biological applications such as manufacturing, computer science and telecommunications. Under the IGMS grant, the PI will spend a year visiting the Systems Biodynamics Lab in the Bioengineering Department at UCSD. Her hosts will be the leaders of the lab, Drs. Jeff Hasty and Lev Tsimring. Being physically based in the Systems Biodynamics Lab will allow the PI to interact on a day-to-day basis with researchers there. Especially important in this regard will be the opportunity to interact with those performing experiments, so that mathematical models and associated analyses can be informed by the results of experiments and conversely the design of experiments can be informed by the analysis of mathematical models. The IGMS grant will enable the PI to acquire the new knowledge and experience to expand her research to applications in synthetic biology. In particular, it will enable her to participate in interdisciplinary research in synthetic biology, to mentor undergraduate and graduate students in synthetic biology, and to direct mathematics Ph.D. students on projects with applications in synthetic biology.

The University of California-San Diego is a premier research university with a focus on the STEM disciplines. In the current proposed project, the institution seeks to implement a multi-pronged approach toward a longitudinal social science study that will identify and analyze mechanism of cumulative disadvantage for women, minorities and LGBT faculty in the STEM fields. The two primary research questions include a focus on the disproportionate cumulative disadvantage of special populations of STEM faculty and on means by which disadvantages at the discipline, department and individual levels lead to disparities in career outcomes. Specific methodological tools that will be used to facilitate this project are longitudinal panel surveys, longitudinal salary analyses, salary and productivity analyses and interviews with various faculty from underrepresented groups.

Intellectual Merit
The proposed project will study the specific mechanisms of cumulative disadvantage for women, URM, and LGBT faculty across a four-year period with the goal of identifying individual, departmental, and disciplinary factors that influence a host of outcome variables (e.g., pay, productivity, advancement). The concept of cumulative disadvantage has been studied with computer simulations and qualitatively, but this proposed project represents the first, primarily quantitative investigation of an issue central to understanding the circumstances of various faculty groups.

Broader Impact
The University of California-San Diego project proposes to examine the impact of cumulative disadvantage for women, underrepresented minorities and LGBT faculty in the academic STEM disciplines that results in disparities in career outcomes. As such, the project will have a broad impact on special populations of women faculty who have been largely underserved by the ADVANCE community. This study represents the first of its kind and, if successful will contribute tremendously to advancing current knowledge regarding the underrepresentation of women faculty from a broad range of perspectives.