Recorded lecture videos are an increasingly important learning resource. However, traditional video format does not allow quick navigation to the desired content of interest. Recent research has enhanced navigation by dividing lecture videos into chapters and creating a summary of each chapter. The visual content on lecture video frames represents a valuable source of information for identifying topic boundaries as well as summarizing content. The focus of the research presented in this paper is to accurately identify visual objects in lecture video frames. The methods developed for camera videos are not directly applicable here as the visual content includes charts, graphs, and illustrations intermingled with text. A common approach based on locating regions with continuous pixel changes has a key limitation that logically consistent visual objects can have modest size gaps inside them. The result is over-segmentation, where a logical object is split into multiple objects if the gap threshold is too low, or under-segmentation, where adjacent objects are recognized as a single large object if the gap threshold is too high. This paper introduces a novel approach that exploits the observation that components of logical objects often have color and geometrical similarity. In our methodology, first a relatively large number of visual elements are identified with a small gap threshold. Subsequently, these visual elements are selectively combined using gap along with color and geometrical similarity. An evaluation was conducted with a suite of 170 lecture video frames from STEM coursework. The results demonstrate the significant impact of color and geometry in improving the accuracy of visual object identification in lecture video frames.

Automatic discovery of keywords for lecture video segments is an important component of advanced navigation systems for lecture videos. The suitability of a word or a short phrase to be a keyword depends on various factors, including the frequency in a segment, relative frequency in reference to the full video, font size, time on screen, and the existence in domain and language dictionaries. The research presented in this paper provides a refined understanding of how various factors contribute to predicting keywords based on logistic regression analysis. The analysis employs a real-world dataset consisting of lecture videos from Biology, Computer Science, and Chemistry, hosted on Videopoints, a lecture video management portal. Term frequency, maximum font size, and presence in a domain dictionary were identified as the most important predictors of keywords. The results provide a scientific foundation and valuable insights into the design of future keyword prediction systems.

Lecture video is an increasingly important learning resource. However, the challenge of quickly finding the content of interest in a long lecture video is a critical limitation of this format. This paper introduces automatic discovery of keywords (or tags) for lecture video segments to improve navigation. A lecture video is divided into topical segments based on the frame-to-frame similarity of content. A user navigates the lecture video assisted by visual summaries and keywords for the segments. Keywords provide an overview of the content discussed in the segment to improve navigation. The input to the keyword identification algorithm is the text from the video frames extracted by OCR. Automatically discovering keywords is challenging as the suitability of an N-gram to be a keyword depends on a variety of factors including frequency in a segment and relative frequency in reference to the full video, font size, time on screen, and the existence in domain and language dictionaries. This paper explores how these factors are quantified and combined to identify good keywords. The key scientific contribution of this paper is the design, implementation, and evaluation of a keyword selection algorithm for lecture video segments. Evaluation is performed by comparing the keywords generated by the algorithm with the tags chosen by experts on 121 segments of 11 videos from STEM courses.

The following topics are dealt with: video signal processing; video streaming; feature extraction; deep learning (artificial intelligence); video coding; learning (artificial intelligence); quality of experience; computer aided instruction; convolutional neural nets; image segmentation.

This Innovative Practice Full Paper explores how classroom lecture video analytics can be employed as an instructional resource. Lecture videos supplementing or replacing traditional classroom instruction are common in academic settings, and have been shown to contribute positively to student satisfaction and student academic performance. Lecture video usage patterns also contain information that can be employed by instructors to improve course offerings. This paper presents a video lecture analytics framework that transforms extensive usage data into easily understood visual formats. This analytics suite is part of the Indexed Captioned Searchable (ICS) lecture video system that is widely used at the University of Houston. The paper reports on a case study that contrasts the nature of usage of lecture video in a traditional face-to-face undergraduate course on Human Physiology and a graduate course taught in the flipped classroom format on Introduction to Psychological Statistics. The data provided by the analytics suite is analyzed for usage patterns across students, across lectures, and across the dates that the course is active, in order to develop insights into the course content and student behavior. The paper illustrates how lecture video analytics can be employed by an instructor to understand student behavior and improve coursework.

Summary Volunteer PC hosts represent massive computation capacity at a low cost but are challenging to employ for general parallel computing. This paper presents the design, execution model, implementation, and evaluation of the Volpex framework for robust execution of parallel codes on volunteer PC grids characterized by system and network heterogeneity, varying availability, and frequent failures. The communication model is based on one‐sided Put/Get calls to an abstract global shared space enhanced to support multiple autonomous instances of the same process at different stages of execution. Our approach customizes and combines the use of replication, checkpointing, and host selection. This presents formidable challenges that are addressed in this work; efficient checkpointing of distributed replicated processes, dynamic management of redundancy, quick restart in a distributed environment, and application specific host selection. The integrated runtime system is shown to effectively execute moderate size, coarse‐grain, communicating codes on a worldwide distributed volunteer environment, a new milestone in volunteer computing. Extensive evaluation is conducted with example scientific codes on a pool of around 600 volunteer hosts. The results demonstrate the trade‐offs in deploying checkpointing, redundancy, and host selection, and how these methods combine to provide application performance that is close to the ideal failure free performance.

Non-intrusive occupant identification enables numerous applications in Smart Buildings such as personalization of climate and lighting. Current techniques do not scale beyond 20 people, whereas commercial buildings have 100 or more people. This article proposes a new method to identify occupants by sensing their body shape, movement, and walking patterns as they walk through a SonicDoor, a door instrumented with three ultrasonic sensors. The proposed method infers contextual information, such as paths and historical walks through different doors of the building. Each SonicDoor is instrumented with ultrasonic ping sensors, one on top sensing height and two on the sides of the door sensing width of the person walking through the door. SonicDoor detects a walking event and analyzes it to infer whether the Walker is using a phone, holding a handbag, or wearing a backpack. It extracts a set of features from the walking event and corrects them using a set of transformation functions to mitigate the bias. We deployed five SonicDoors in a real building for two months and collected data consisting of over 9,000 walking events spanning over 170 people. The proposed method identifies 100 occupants with an accuracy of 90.2%, which makes it suitable for commercial buildings.

Due to the growing size of compute clusters, large scale parallel applications increasingly have to deal with hardware malfunctions and other failure scenarios during execution. The overall goal of this research is to get good performance of MapReduce applications despite failures. The paper focuses on evaluation of the performance of two representative Hadoop MapReduce applications, 'WordCount' and 'Stack Exchange', with different execution parameters and under different failure scenarios. The paper also presents different options to inject failures into MapReduce applications to simulate real world failures. Some of the preliminary observations are that slowdown due to failure is higher with relatively larger input split sizes, slowdown peaks near the optimal split size, and that the performance and slowdown are sensitive to key MapReduce execution parameters.

Volunteer computing is being used successfully for large scale scientific computations. This research is in the context of Volpex, a programming framework that supports communicating parallel processes in a volunteer environment. Redundancy and checkpointing are combined to ensure consistent forward progress with Volpex in this unique execution environment characterized by heterogeneous failure prone nodes and interdependent replicated processes. An important parameter for optimizing performance with Volpex is the frequency of checkpointing. The paper presents a mathematical model to minimize the completion time for inter-dependent parallel processes running in a volunteer environment by finding a suitable checkpoint interval. Validation is performed with a sample real world application running on a pool of distributed volunteer nodes. The results indicate that the performance with our predicted checkpoint interval is fairly close to the best performance obtained empirically by varying the checkpoint interval.

We present DwarfCode, a performance prediction tool for MPI applications on diverse computing platforms. The goal is to accurately predict the running time of applications for task scheduling and job migration. First, DwarfCode collects the execution traces to record the computing and communication events. Then, it merges the traces from different processes into a single trace. After that, DwarfCode identifies and compresses the repeating patterns in the final trace to shrink the size of the events. Finally, a dwarf code is generated to mimic the original program behavior. This smaller running benchmark is replayed in the target platform to predict the performance of the original application. In order to generate such a benchmark, two major challenges are to reduce the time complexity of trace merging and repeat compression algorithms. We propose an O(mpn) trace merging algorithm to combine the traces generated by separate MPI processes, where m denotes the upper bound of tracing distance, p denotes the number of processes, and n denotes the maximum of event numbers of all the traces. More importantly, we put forward a novel repeat compression algorithm, whose time complexity is O(nlogn). Experimental results show that DwarfCode can accurately predict the running time of MPI applications. The error rate is below 10 percent for compute and communication intensive applications. This toolkit has been released for free download as a GNU General Public License v3 software.

Video of classroom lectures is a valuable and increasingly popular learning resource. A major weakness of the video format is the inability to quickly access the content of interest. The goal of this work is to automatically partition a lecture video into topical segments which are then presented to the user in a customized video player. The approach taken in this work is to identify topics based on text similarities across the video. The paper investigates the use of screen text extracted by Optical Character Recognition tools, as well as the speech text extracted by Automatic Speech Recognition tools. An automatic text-based segmentation algorithm is developed to identify topic changes and evaluated on a set of twenty-five lecture videos. The key conclusions are as follows. Screen text is a better guide to discovering topic changes than speech text, the effectiveness of speech text can be improved significantly with the correction of speech text, and combining screen text and accurate speech text can improve accuracy. Results are presented from surveys showing a high level of satisfaction among student users of automatically segmented videos. The paper also discusses the limits of automatic segmentation and the reasons why it is far from perfect.

This paper describes a large-scale study of student use and perceived value of videos of faculty lectures as an additional learning resource. The survey-based study was conducted with ~2,300 college students in biology, chemistry, computer science, geology, and mathematics. The study provides a nuanced understanding of the nature and frequency of students' video usage; student perceptions of value of video use; and differences in use and value by students representing different groups (field of study; student demographics; demands on students' time; students' goals, previous experience, and commitment to education). Most students used the videos and a very strong majority valued them as a learning resource Students with longer commute times were more likely to use the videos. No evidence was found that videos are used in place of going to class. On the contrary, students who used more videos also were more likely to attend class. Students overwhelmingly valued the finding tools (index and search). The value that students place on video lectures as a learning resource exceeds expectations. This study contributes to the growing body of evidence that making video lectures available, especially when they have features that aid finding specific sections, is worth faculty time.

Video of a classroom lecture has been shown to be a versatile learning resource comparable to a textbook. Captions in videos are highly valued by students, especially those with hearing disability and those whose first language is not English. Captioning by automatic speech recognition (ASR) tools is of limited use because of low and variable accuracy. Manual captioning with existing tools is a slow, tedious and expensive task. In this work, we present a web-based crowdsourcing editor to add or correct captions for video lectures. The editor allows a group, e.g., students in a class, to correct the captions for different parts of a video lecture simultaneously. Users can review and correct each other's work. The caption editor has been successfully employed to caption STEM coursework videos. Our findings based on survey results and interviews indicate that this innovative crowdsourcing tool is effective and efficient for captioning lecture videos and has considerable value in educational practice. The caption editor is integrated with Indexed Captioned Searchable (ICS) Videos framework at University of Houston that has been used by dozens of courses and 1000s of students. The ICS Videos framework including the captioning tool is open source software available to educational institutions.

Mapping of MPI processes to the available resources is an increasingly complex but important task on modern parallel systems. This paper presents a new approach to optimize the process placement of a parallel application based on its I/O access pattern. The paper introduces the SetMatch process mapping algorithm, which significantly reduces the cost of the communication occurring in collective I/O operations. The effectiveness of the approach has been evaluated for multiple scenarios on a PVFS2 file system. Our results demonstrate significant improvements in the communication time of collective I/O operations as well as improvements in the overall application execution time with our mapping strategy. The generalized SetMatch algorithm was the only mapping strategy that was able to provide adequate performance for all scenarios used in this paper.

A pool of distributed volunteer PCs presents an extremely hostile environment for execution of communicating parallel codes due to system and network heterogeneity, varying availability, and frequent failures. Well known methods for fault tolerance, specifically replication and check pointing, are challenging to deploy and not sufficient individually to provide continuous forward application progress. As the failure of a single logical process leads to application failure, the degree of redundancy needed for long running applications is too large to be practical. Check pointing and rollback does not provide protection against slow and variable speed nodes and is impractical when system wide MTBF is in minutes or less, common for a moderate size volunteer computing pool. The approach taken in this research is to exploit both, but that presents formidable challenges, efficient check pointing of distributed replicated processes, dynamic management of redundancy, quick restart in a distributed environment, and others. Proposed solution also leverages node selection based on availability prediction. The integrated runtime system is shown to effectively execute moderate size, coarse grain, communicating codes on a worldwide distributed volunteer environment, a new milestone in volunteer computing. The results provide new insight into how multiple techniques interact and contribute to robustness. The programming model is based on one-sided Put/Get calls to an abstract global shared space that works seamlessly with replicated processes. A Replica Exchange Molecular Dynamics code is employed to drive evaluation. The execution environment includes hosts on a University campus as well as hosts distributed around the world.

Videos of classroom lectures have proven to be a popular and versatile learning resource. This paper reports on videos featuring Indexing, Captioning, and Search capability (ICS Videos). The goal is to allow a user to rapidly search and access a topic of interest, a key shortcoming of the standard video format. A lecture is automatically divided into logical indexed video segments by analyzing video frames. Text is automatically identified with OCR technology enhanced with image transformations to drive keyword search. Captions can be added to videos. The ICS video player integrates indexing, search, and captioning in video playback and has been used by dozens of courses and 1000s of students. This paper reports on the development and evaluation of ICS videos framework and assessment of its value as an academic learning resource.

Volunteer PC grids represent massive computation capacity at a low cost, but are challenging to employ for parallel computing because of variable and unpredictable performance and availability. A communicating parallel program must employ explicit redundancy, or implicit redundancy with uncoordinated checkpoint-restart to make continuous forward progress in such an unreliable environment. A communication model based on one-sided Put/Get calls to an abstract global shared space is a good match as processes can execute their communication operations independently and asynchronously. However, no existing system is designed for redundant communicating processes. The key problem is that a single logical operation that impacts the global program state may be executed by different instances of the same process at different times leading to semantic inconsistency. This paper presents the design, execution model, implementation, and usage of {\em Volpex}, a communication layer for robust execution on volunteer PC grids. The research leads to a practical way to employ idle PCs for latency tolerant parallel computing applications.

Idle desktops have been successfully used to run sequential and master-slave task parallel codes on a large scale in the context of volunteer computing. However, execution of message passing parallel programs in such environments is challenging because a pool of nodes to execute an application may have architectural and operating system heterogeneity, can include widely distributed nodes across security domains, and nodes may become unavailable for computation frequently and without warning. The VolPEx (Parallel Execution on Volatile Nodes) tool set is building MPI support in such environments based on selective use of process redundancy and message logging. However, addressing this challenge requires tradeoffs between performance, portability, and usability. The paper introduces a robust MPI library that is designed to be highly portable across heterogeneous architectures and operating systems. This VolpexPyMPI library is built with Python, works with Linux and Windows platforms and accepts user level MPI programs written in C or FORTRAN. The performance of VolpexPyMPI is compared with a traditional C based implementation of MPI. The paper examines in detail the tradeoffs of these usability focused and performance focused approaches.

Execution and communication traces are central to performance modeling and analysis. Since the traces can be very long, meaningful compression and extraction of representative behavior is important. Commonly used compression procedures identify repeating patterns in sections of the input string and replace each instance with a representative symbol. This can prevent the identification of long repeating sequences corresponding to outer loops in a trace. This paper introduces and analyzes a framework for identifying the maximal loop nest from a trace. The discovery of loop nests makes construction of compressed representative traces straightforward. The paper also introduces a greedy algorithm for fast ``near optimal'' loop nest discovery with well defined bounds. Results of compressing MPI communication traces of NAS parallel benchmarks show that both algorithms identified the basic loop structures correctly. The greedy algorithm was also very efficient with an average processing time of 16.5 seconds for an average trace length of 71695 MPI events.

Converged fabrics that support data, storage, and cluster networking in a unified fashion are desirable for their cost and manageability advantages. Recent trends towards higher-bandwidths in commodity networks, physical-layer similarities across different communication protocols, and the adoption of blade servers along with the corresponding availability of ‘backplanes’ to implement new networking methods, motivate revisiting this idea. We discuss various aspects of fabric convergence, and present some evaluation results from our experiments in the context of a specific I/O consolidation case study. Based on the insights from these experiments, we discuss opportunities for future research - in new instrumentation and evaluation methods, new cross-layer and application-agnostic designs for fabric convergence solutions, and new system architectures that leverage ensemble-level resource sharing. Our goal, through the discussions in this position paper, is to initiate a more general examination of these issues in the broader academic community.

Increased complexity of memory systems to ameliorate the gap between the speed of processors and memory has made it increasingly harder for compilers to optimize an arbitrary code within a palatable amount of time. With the emergence of multicore (CMP), multiprocessor (SMP) and hybrid shared memory multiprocessor architectures, achieving high e ciency is becoming even more challenging. To address the challenge to achieve high e ciency in performance critical applications, domain speci c frameworks have been developed that aid the compilers in scheduling the computations. We have developed a portable framework for the Fast Fourier Transform (FFT) that achieves high e ciency by automatically adapting to various architectural features. Adapting to parallel architectures by searching through all the combinations of schedules (plans) is an expensive task, even when the search is conducted in parallel. In this paper, we develop heuristics to simplify the generation of better schedules for parallel FFT computations on CMP/SMP systems. We evaluate the performance of OpenMP and PThreads implementations of FFT on a number of latest architectures. The performance of parallel FFT schedules is compared with that of the best plan generated for sequential FFT and the speedup for di erent number of processors is reported. In the end, we also present a performance comparison between the UHFFT and FFTW implementations.

Online learning, defined broadly as recording and delivering classroom experience with technology, has tremendous potential. However, success to date has been very limited in science and engineering. We believe this is because traditional video recording is cumbersome and not suitable for technical lectures and removing live classroom interaction is detrimental to learning. Employing Tablet PCs with slide presentation software has made it simple and convenient to develop and record high quality lectures. We employ such videos in a hybrid model of coursework. All lectures are made available as online videos, but limited classroom interaction is an important component; the classroom is used for review of lecture material, examinations, demonstrations, tutorials, and hands-on sessions. The hybrid framework is particularly suitable for students with logistical difficulties, e.g., because of work schedule. This paper is an evaluation of the hybrid learning approach as applied to upper level computer science coursework. We report our experience in teaching a suite of hybrid courses at the University of Houston and discuss the detailed feedback we received from the students who participated in the courses.

Parallel machines are typically space shared, or time shared such that only one application executes on a group of nodes at any given time. It is generally assumed that executing multiple parallel applications simultaneously on a group of independently scheduled nodes is not efficient because of synchronization requirements. The central contribution of this paper is to demonstrate that performance of parallel applications with sharing is typically competitive for independent and coordinated (gang) scheduling on small compute clusters. There is a modest overhead due to uncoordinated scheduling but it is often compensated by better sharing of resources. The impact of sharing was studied for different numbers of nodes and threads and different memory and CPU requirements of competing applications. The significance of the CPU time slice, a key parameter in CPU scheduling, was also studied. Application characteristics and operating system scheduling policies are identified as the main factors that influence performance with node sharing. All experiments are performed with NAS benchmarks on a Linux cluster. The significance of this research is that it provides evidence to support flexible and decentralized scheduling and resource selection policies for cluster and grid environments.

The ability to quickly predict the throughput of a TCP transfer between a client and a server, or between peers, has wide application in scientific computing and commercial computing. This paper presents a new approach to fast prediction of overall throughput of a large TCP file transfer. The method constructs the time series of windows of segments arriving at the receiver, and predicts future throughput by exploiting knowledge of how TCP manages transfer window size. When the file transfer time series resembles a known TCP pattern, this information is utilized for prediction, otherwise simple heuristics are used. We have compared TCP pattern based prediction against traditional methods like a simple moving average, exponential weighted moving average, and aggregate measured throughput on a large suite of real life TCP traces. Our results show that TCP pattern based prediction generally performs as well or better than the best of other methods in any given scenario.

The performance skeleton of an application is a short running program whose performance in any scenario reflects the performance of the application it represents. Such a skeleton can be employed to quickly estimate the performance of a large application under existing network and node sharing. This work presents and validates a framework for automatic construction of performance skeletons of parallel applications. The approach is based on capturing the compute and communication behavior of an executing application, summarizing this behavior and then generating a synthetic skeleton program based on the summarized information. We demonstrate that automatically generated performance skeletons take an order of magnitude less time to execute than the application they represent, yet predict the application execution time with reasonable accuracy. For the NAS benchmark suite, we observed that the average-error in predicting the execution time was 6%. This research is motivated by the problem of performance driven resource selection in shared network and Grid environments.

A central problem in executing performance critical parallel and distributed applications on shared networks is the selection of computation nodes and communication paths for execution. Automatic selection of nodes is complex as the best choice depends on the application structure as well as the expected availability of computation and communication resources. This paper presents a solution to this problem for realistic application and network scenarios. A new algorithm to jointly analyze computation and communication resources for different application demands is introduced and a framework for automatic node selection is developed on top of Remos, which is a query interface to network information. The paper reports results from a set of applications, including Airshed pollution modeling and magnetic resonance imaging, executing on a high speed network testbed. The results demonstrate that node selection is effective in enhancing application performance in the presence of computation load as well as network traffic. Under the network conditions used for experiments, the increase in execution time due to compute loads and network congestion was reduced by half with node selection. The node selection algorithms developed in this research are also applicable to dynamic migration of long running jobs.

Development of portable network-aware applications demands an interface to the network that allows an application to obtain information about its execution environment. The paper motivates and describes the design of Remos, an API that allows network-aware applications to obtain relevant information. The major challenges in defining a uniform interface are network heterogeneity, diversity in traffic requirements, variability of the information, and resource sharing in the network. Remos addresses these issues with two abstraction levels, explicit management of resource sharing, and statistical measurements. The flows abstraction captures the communication between nodes, and the topologies abstraction provides a logical view of network connectivity. Remos measurements are made at network level, and therefore information to manage sharing of resources is available. Remos is designed to deliver best effort information to applications, and it explicitly adds statistical reliability and variability measures to the core information. The paper also presents preliminary results and experience with a prototype Remos implementation for a high speed IP based network testbed.

High Performance Fortran (HPF) has emerged as a standard language fordata parallel computing. However, a wide variety of scientific applications are best programmed by a combination of task and data parallelism. Therefore, a good model of task parallelism is important for continued success of HPF for parallel programming. This paper presents a task parallelism model that is simple, elegant, and relatively easy to implement in an HPF environment. Task parallelism is exploited by mechanisms for dividing processors into subgroups and mapping computations and data onto processor subgroups. This model of task parallelism has been implemented in the Fx compiler at Carnegie Mellon University. The paper addresses the main issues in compiling integrated task and data parallel programs and reports on the use of this model for programming various flat and nested task structures. Performance results are presented for a set of programs spanning signal processing, image processing, computer vision and environment modeling. A variant of this task model is a new approved extension of HPF and this paper offers insight into the power of expression and ease of implementation of this extension.

Parallel languages allow the programmer to express parallelism at a high level. The management of parallelism and the generation of interprocessor communication is left to the compiler and the runtime system. This approach to parallel programming is particularly attractive if a suitable widely accepted parallel language is available. High Performance Fortran (HPF) has emerged as the first popular machine independent parallel language, and remarkable progress has been made towards compiling HPF efficiently. However, the performance of HPF programs is often poor and unpredictable, and obtaining adequate performance is a major stumbling block that must be overcome if HPF is to gain widespread acceptance. The programmer is often in the dark about how to improve the performance of an HPF program since poor performance can be attributed to a variety of reasons, including poor choice of algorithm, limited use of parallelism, or an inefficient data mapping. This paper presents a profiling tool that allows the programmer to identify the regions of the program that execute inefficiently, and to focus on the potential causes of poor performance. The central idea is to distinguish the code that is executing efficiently from the code that is executing poorly. Efficient code uses all processors of a parallel system to make progress, while inefficient code causes processors to wait, execute replicated code, idle, communicate, or perform compiler bookkeeping. We designate the latter code as non-scalable, since adding more processors generally does not lead to improved performance for such code. By analogy, the former code is called scalable. The tool presented here separates a program into scalable and non-scalable components and identifies the causes of non-scalability of different components. We show that compiler information is the key to dividing the execution times into logical categories that are meaningful to the programmer. We present the design and implementation of a profiler that is integrated with Fx, a compiler for a variant of HPF. The paper includes two examples that demonstrate how the data reported by the profiler are used to identify and resolve performance bugs in parallel programs. © 1997 John Wiley & Sons, Ltd.

This paper addresses job scheduling for parallel supercomputers. Modern parallel systems with n nodes can be used by jobs requesting up to n nodes. If less than n nodes are requested, multiple jobs can be run at the same time, allowing several users to use the system. One of the challenges for the operating system is to give reasonable service to a diverse group of requests. A single 1-node job that is running for a long time may effectively block the whole machine if the next job requests all n nodes. To date various policies have been proposed for the scheduling highly parallel computers. But as the users of current supercomputers know, these policies work far from perfect. This paper reports on the measurement of the usage of a 96-node Intel Paragon at ETH Zurich, a 512 node IBM SP2 at Cornell Theory Center, and a 512 node Cray T3D at Pittsburgh Supercomputing Center. We discuss the common characteristics of the different workloads and identify their impact on job scheduling techniques for such parallel systems. The metrics used for evaluating scheduling are based on turnaround time and fairness among jobs. We specifically show how two simple scheduling optimizations based on reordering the waiting queue can be used to effectively improve scheduling performance on real workloads. An important contribution of this paper is to establish that supercomputer workloads do exhibit some common characteristics but they also differ in important ways, and the knowledge of workloads is important for design of effective scheduling algorithms. Given the current ad-hoc approach applied to tuning the scheduler systems, these results are of interest to scheduling researchers, supercomputer installations, and developers of scheduling software.

This paper addressesoptimal mapping of parallel programs tool in the Fx parallelizing compiler for a dialect of High Performance Fortran.

Many applications in a variety of domains including digital signal processing, image processing and computer vision are composed of a sequence of tasks that act on a stream of input data sets in a pipelined manner. Recent research has established that these applications are best mapped to a massively parallel machine by dividing the tasks into modules and assigning a subset of the available processors to each module. This paper addresses the problem of optimally mapping such applications onto a massively parallel machine. We formulate the problem of optimizing throughput in task pipelines and present two new solution algorithms. The formulation uses a general and realistic model for inter-task communication, takes memory constraints into account, and addresses the entire problem of mapping which includes clustering tasks into modules, assignment of processors to modules, and possible replication of modules. The first algorithm is based on dynamic programming and finds the optimal mapping of k tasks onto P processors in O(P4k2) time. We also present a heuristic algorithm that is linear in the number of processors and establish with theoretical and practical results that the solutions obtained are optimal in practical situations. The entire framework is implemented as an automatic mapping tool for the Fx parallelizing compiler for High Performance Fortran. We present experimental results that demonstrate the importance of choosing a good mapping and show that the methods presented yield efficient mappings and predict optimal performance accurately.

We present a new method to determine whether a convex region contains any integer points. The method is designed for array subscript analysis in parallel programs. The general problem is whether a system of linear equalities and inequalities has an integer solution. A set of known techniques is used to transform the problem to that of finding whether a convex region contains any integer points. The main result of the paper is a set of new search procedures that identify an integer solution in a convex region, or prove that no integer solutions exist. They are based on the geometrical properties of convex regions that are not empty, but also do not contain any integer points. The results contribute to exact and efficient dependence and synchronization analysis of parallel programs.>

For a wide variety of applications, both task and data parallelism must be exploited to achieve the best possible performance on a multicomputer. Recent research has underlined the importance of exploiting task and data parallelism in a single compiler framework, and such a compiler can map a single source program in many different ways onto a parallel machine. The tradeoffs between task and data parallelism are complex and depend on the characteristics of the program to be executed, most significantly the memory and communication requirements, and the performance parameters of the target parallel machine. We present a framework to isolate and examine the specific characteristics of programs that determine the performance for different mappings. Our focus is on applications that process a stream of input, and whose computation structure is fairly static and predictable. We describe three such applications that were developed with our compiler: fast Fourier transforms, narrowband tracking radar; and multibaseline stereo. We examine the tradeoffs between various mappings for them and show how the framework is used to obtain efficient mappings.>

For many applications, achieving good performance on a private memory parallel computer requires exploiting data parallelism as well as task parallelism. Depending on the size of the input data set and the number of nodes (i.e., processors), different tradeoffs between task and data parallelism are appropriate for a parallel system. Most existing compilers focus on only one of data parallelism and task parallelism. Therefore, to achieve the desired results, the programmer must separately program the data and task parallelism. We have taken a unified approach to exploiting both kinds of parallelism in a single framework with an existing language. This approach eases the task of programming and exposes the tradeoffs between data and task parallelism to the compiler. We have implemented a parallelizing Fortran compiler for the iWarp system based on this approach. We discuss the design of our compiler, and present performance results to validate our approach. 1 Introduction Many applicati...

This paper describes a new approach for automatic generation of ejj$cien~parallel programsfiom sequential blocked lin-

Understanding synchronization is important for a parallel programming tool that uses dependence analysis as the basis for advising programmers on the correctness of parallel constructs. This paper discusses static analysis methods that can be applied to parallel programs with event variable synchronization. The objective is to be able to predict potential data races in a parallel program. The focus is on how dependencies and synchronization statements inside loops can be used to analyze complete programs with parallel loop and parallel case style parallelism.

The ParaScope project is building an integrated collection of tools to help scientific programmers develop correct and efficient parallel programs. The centerpiece of this collection is the ParaScope Editor, an intelligent interactive editor for parallel FORTRAN programs. The ParaScope Editor displays data dependencies, which correspond to potential data races among the iterations of a parallel loop, to assist the user in determining the correctness of a proposed parallelization. In addition, it uses dependencies to support a variety of program transformations selectable by the programmer.