In this paper, we develop a method for extracting information from Large Language Models (LLMs) with associated confidence estimates. We propose that effective confidence models may be designed using a large number of uncertainty measures (i.e., variables that are only weakly predictive of - but positively correlated with - information correctness) as inputs. We trained a confidence model that uses 20 handcrafted uncertainty measures to predict GPT-4’s ability to reproduce species occurrence data from iDigBio and found that, if we only consider occurrence claims that are placed in the top 30% of confidence estimates, we can increase prediction accuracy from 57% to 88% for species absence predictions and from 77% to 86% for species presence predictions. Using the same confidence model, we used GPT-4 to extract new data that extrapolates beyond the occurrence records in iDigBio and used the results to visualize geographic distributions for four individual species. More generally, this represents a novel use case for LLMs in generating credible pseudo data for applications in which high-quality curated data are unavailable or inaccessible.

The information stored in biological collections can help us model biodiversity, develop new medicines, control agricultural pests, and understand or avoid epidemics, among many other benefits. The digitization of this information, including the transcription of the Darwin Core (DC) terms from the text in photographs, is currently performed through human-oriented processes that rely on input from experts or consensus from crowdsourced work. Previous studies utilized heuristics, only applicable to a couple of DC terms, for their semi-automated extraction. In this paper, we propose a human-in-the-loop workflow for the general extraction of DC terms. The workflow utilizes crowdsourced data to iteratively train a named-entity recognition model for the extraction of the DC terms. Because the source text can contain errors from the optical character recognition process, the extracted values are validated by a confidence estimation structure of frequency lists. These lists are created from millions of previously digitized records, of other collections, and data already extracted from the collection being processed. The proposed human-in-the-loop approach accelerates the transcription of DC terms by partially automating the extraction of values with a near-human quality. The named-entity recognition model was tested in the extraction of a heterogeneous group of 10 terms, obtaining a recall of 0.859, precision of 0.931, and similarity to the ground-truth data of 0.941, on average. The number of required crowdsourcing sessions was reduced by 84%.

In the last decade, institutions from around the world have implemented initiatives for digitizing biological collections (biocollections) and sharing their information online. The transcription of the metadata from photographs of specimens' labels is performed through human-centered approaches (e.g., crowdsourcing) because fully automated Information Extraction (IE) methods still generate a significant number of errors. The integration of human and machine tasks has been proposed to accelerate the IE from the billions of specimens waiting to be digitized. Nevertheless, in order to conduct research and trying new techniques, IE practitioners need to prepare sets of images, crowdsourcing experiments, recruit volunteers, process the transcriptions, generate ground truth values, program automated methods, etc. These research resources and processes require time and effort to be developed and architected into a functional system. In this paper, we present a simulator intended to accelerate the ability to experiment with workflows for extracting Darwin Core (DC) terms from images of specimens. The so-called HuMaIN Simulator includes the engine, the human-machine IE workflows for three DC terms, the code of the automated IE methods, crowdsourced and ground truth transcriptions of the DC terms of three biocollections, and several experiments that exemplify its potential use. The simulator adds Human-in-the-loop capabilities, for iterative IE and research on optimal methods. Its practical design permits the quick definition, customization, and implementation of experimental IE scenarios.

Hadoop is a popular data-analytics platform based on the MapReduce model. When analyzing extremely big data, hard disk drives are commonly used and Hadoop performance can be optimized by improving I/O performance. Hard disk drives have different performance depending on whether data are placed in the outer or inner disk zones. In this paper, we propose a method that uses knowledge of job characteristics to place data in hard disk drives so that Hadoop performance is improved. Files of a job that intensively and sequentially accesses the storage device are placed in outer disk tracks which have higher sequential access speed than inner tracks. Temporary and permanent files are placed in the outer and inner zones, respectively. This enables repeated usage of the faster zones by avoiding the use of the fastest zones by permanent files. Our evaluation demonstrates that the proposed method improves the performance of the Hadoop jobs by 15.0% over the normal case when file placement is not used. The proposed method also outperforms a previously proposed placement approach by 9.9%.

Information Extraction (IE) from imaged text is affected by the output quality of the text-recognition process. Misspelled or missing text may propagate errors or even preclude IE. Low confidence in automated methods is the reason why some IE projects rely exclusively on human work (crowdsourcing). That is the case of biological collections (biocollections), where the metadata (Darwin-core Terms) found in digitized labels are transcribed by citizen scientists. In this paper, we present an approach to reduce the number of crowdsourcing tasks required to obtain the transcription of the text found in biocollections' images. By using an ensemble of Optical Character Recognition (OCR) engines - OCRopus, Tesseract, and the Google Cloud OCR - our approach identifies the lines and characters that have a high probability of being correct. This reduces the need for crowdsourced transcription to be done for only low confidence fragments of text. The number of lines to transcribe is also reduced through hybrid human-machine crowdsourcing where the output of the ensemble of OCRs is used as the first "human" transcription of the redundant crowdsourcing process. Our approach was tested in six biocollections (2,966 images), reducing the number of crowdsourcing tasks by 76% (58% due to lines accepted by the ensemble of OCRs and about 18% due to accelerated convergence when using hybrid crowdsourcing). The automatically extracted text presented a character error rate of 0.001 (0.1%).

Many big-data processing jobs use data-analytics frameworks such as Apache Hadoop (currently also known as YARN). Such frameworks have tunable configuration parameters set by experienced system administrators and/or job developers. However, tuning parameters manually can be hard and time-consuming because it requires domain-specific knowledge and understanding of complex inter-dependencies among parameters. Most of the frameworks seek efficient resource management by assigning resource units to jobs, the maximum number of units allowed in a system being part of the static configuration of the system. This static resource management has limited effectiveness in coping with job diversity and workload dynamics, even in the case of a single job. The work reported in this article seeks to improve performance (e.g., multiple-jobs makespan and job completion time) without modification of either the framework or the applications and avoiding problems of previous self-tuning approaches based on performance models or resource usage. These problems include (1) the need for time-consuming training, typically offline and (2) unsuitability for multi-jobs/tenant environments. This article proposes a hierarchical self-tuning approach using (1) a fuzzy-logic controller to dynamically adjust the maximum number of concurrent jobs and (2) additional controllers (one for each cluster node) to adjust the maximum number of resource units assigned to jobs on each node. The fuzzy-logic controller uses fuzzy rules based on a concave-downward relationship between aggregate CPU usage and the number of concurrent jobs. The other controllers use a heuristic algorithm to adjust the number of resource units on the basis of both CPU and disk IO usage by jobs. To manage the maximum number of available resource units in each node, the controllers also take resource usage by other processes (e.g., system processes) into account. A prototype of our approach was implemented for Apache Hadoop on a cluster running at CloudLab. The proposed approach was demonstrated and evaluated with workloads composed of jobs with similar resource usage patterns as well as other realistic mixed-pattern workloads synthesized by SWIM, a statistical workload injector for MapReduce. The evaluation shows that the proposed approach yields up to a 48% reduction of the jobs makespan that results from using Hadoop-default settings.

High-performance I/O is essential for big-data analyses. Modern storage systems utilize HDDs and SSDs mainly for achieving large capacity and high performance, respectively. Using an SSD as a cache for accesses to HDDs is one of the promising methods for improving large-scale I/O performance in modern computers. In addition, M.2 is increasing its importance in high-performance I/O processing. In this paper, we investigate the I/O performance of storage systems including M.2 SSD and SSD cache. Our experimental results show that big-data processing performance can improve significantly by using an M.2 SSD cache.

Biological collections store information with broad societal and environmental impact. In the last 15 years, after worldwide investments and crowdsourcing efforts, 25% of the collected specimens have been digitized; a process that includes the imaging of text attached to specimens and subsequent extraction of information from the resulting image. This information extraction (IE) process is complex, thus slow and typically involving human tasks. We propose a hybrid (Human-Machine) information extraction model that efficiently uses resources of different cost (machines, volunteers and/or experts) and speeds up the biocollections' digitization process, while striving to maintain the same quality as human-only IE processes. In the proposed model, called SELFIE, self-aware IE processes determine whether their output quality is satisfactory. If the quality is unsatisfactory, additional or alternative processes that yield higher quality output at higher cost are triggered. The effectiveness of this model is demonstrated by three SELFIE workflows for the extraction of Darwin-core terms from specimens' images. Compared to the traditional human-driven IE approach, SELFIE workflows showed, on average, a reduction of 27% in the information-capture time and a decrease of 32% in the required number of humans and their associated cost, while the quality of the results was negligibly reduced by 0.27%.

Summary The Pacific Rim Application and Grid Middleware Assembly (PRAGMA) is an international community of researchers that actively collaborate to address problems and challenges of common interest in eScience. The PRAGMA Experimental Network Testbed (PRAGMA‐ENT) was established with the goal of constructing an international software‐defined network (SDN) testbed to offer the necessary networking support to the PRAGMA cyberinfrastructure. PRAGMA‐ENT is isolated, and PRAGMA researchers have complete freedom to access network resources to develop, experiment, and evaluate new ideas without the concerns of interfering with production networks. In the first phase, PRAGMA‐ENT focused on establishing an international L2 backbone. With support from the Florida Lambda Rail, Internet2, PacificWave, Japan Gigabit Network, and TaiWan Advanced Research and Education Network, PRAGMA‐ENT backbone connects openflow‐enabled switches at University of Florida, University of California, San Diego, Nara Institute of Science and Technology (Japan), Osaka University (Japan), National Institute of Advanced Industrial Science and Technology (Japan), and National Applied Research Laboratories (Taiwan). The second phase of PRAGMA‐ENT consisted of an evaluation of technologies for the control plane that enables multiple experiments (ie, OpenFlow controllers) to coexist. Preliminary experiments with FlowVisor revealed some limitations leading to the development of a new approach, called AutoVFlow. This paper describes our experience in the establishment of PRAGMA‐ENT backbone (with international L2 links), its current status, and plans for the control plane. Discussion of preliminary application ideas, including optimization of routing control; multipath routing control; extending the backbone using overlay network; and remote visualization are also discussed.

As computational clouds offer increasingly sophisticated services, there is a dramatic increase in the variety and complexity of virtual machine (VM) placement problems. In this paper, we consider a VM placement problem with a special type of anti-colocation requirements-disk anti-colocation-which stipulate that, for every VM assigned to a PM (physical machine), its virtual disks should be spread out across the physical disks of the PM. Once such a requirement is met, the users of the VM can expect improved disk I/O performance. There will also be improvement in fault tolerance and availability. For scalable solutions, we propose a method that combines hierarchical decomposition with mixed integer programming (MIP), where the basic building blocks are independent, small MIP subproblems. We provide experimental results to demonstrate the effectiveness of the proposed method. We show that it is scalable and achieves high performance with respect to the optimization objective.

Computational clouds have evolved to go beyond cost-effective on-demand hosting of IT resources and elasticity. The added features now include the ability to offer entire IT systems as a service that can quickly adapt to changing business environments. The new trend introduces challenges in datacenter resource management, including scalability, system-orientation, and optimization supporting both datacenter efficiency and customer system agility and performance. The conventional approach of resource management adopts a flat fine-grained model that results in problem formulations of enormous sizes, it also has the drawback of being less flexible in meeting customers' need. In this paper, we introduce a pack-centric approach to datacenter resource management by abstracting a system as a pack of resources and considering the mapping of these packs onto physical datacenter resource groups, called swads. The assignments of packs to swads are formulated as mixed integer programming problems. Scalability is achieved through a hierarchical decomposition method and parallel solvers. The new datacenter resource management framework is illustrated with a concrete resource placement problem. Numerical experiments show the scalability of the hierarchical decomposition method and the benefits of the overall framework.

Historical data sources, like medical records or biological collections, consist of unstructured heterogeneous content: handwritten text, different sizes and types of fonts, and text overlapped with lines, images, stamps, and sketches. The information these documents can provide is important, from a historical perspective and mainly because we can learn from it. The automatic digitization of these historical documents is a complex machine learning process that usually produces poor results, requiring costly interventions by experts, who have to transcribe and interpret the content. This paper describes hybrid (Human- and Machine-Intelligent) workflows for scientific data extraction, combining machine-learning and crowdsourcing software elements. Our results demonstrate that the mix of human and machine processes has advantages in data extraction time and quality, when compared to a machine-only workflow. More specifically, we show how OCRopus and Tesseract, two widely used open source Optical Character Recognition (OCR) tools, can improve their accuracy by more than 42%, when text areas are cropped by humans prior to OCR, while the total time can increase or decrease depending on the OCR selection. The digitization of 400 images, with Entomology, Bryophyte, and Lichen specimens, is evaluated following four different approaches: processing the whole specimen image (machine-only), processing crowd cropped labels (hybrid), processing crowd cropped fields (hybrid), and cleaning the machine-only output. As a secondary result, our experiments reveal differences in speed and quality between Tesseract and OCRopus.

Complex software systems come with a huge number of configuration parameters for tuning their performance as well as functionality. It is a challenge for the users of such systems to understand how various parameters interact, and causing them to use the default configuration settings to avoid problems. Studies show that a lot of performance optimization opportunities are missed when complex software systems are run with the default configuration settings. This paper proposes a graph-based representation of configuration parameter interactions that are extracted using a scaleable static analysis approach. Experimental results obtained with a case study on a data analysis framework, Apache Hadoop, suggest that the proposed approach is effective in capturing some of the interactions at the component level.

Summary Self‐caring IT systems are those that can proactively avoid system failures rather than reactively handle failures after they have occurred. In this paper, we focus on failures in which a MapReduce job is unable to execute within an service‐level agreement based completion time. The existing fault‐tolerance capability provided by MapReduce frameworks such as Hadoop, is simple and the penalty associated with handling faults could potentially lead to excessive job execution times. Our goal in this paper is to bring out the severity of this penalty for different job and framework parameters. We quantitatively evaluate the penalty in execution time associated with node faults using the MRPerf simulator. We then perform an empirical study of penalties on a virtualized testbed consisting of Xen domains, by varying system characteristics along four dimensions: hardware, application, dataset, and fault types. Through simulation and empirical results, we show that job‐completion‐time service‐level agreement violations can be reduced using dynamic resource scaling. Scaling leverages, the elastic properties of a virtualized environment, to mitigate execution time penalties and hence proactively avoids a potential job failure. We show that using resource scaling, performance penalties can be decreased to less than 5% of the no‐fault execution time, at minimal additional cost. Copyright © 2013 John Wiley & Sons, Ltd.

Summary There is an increasing number of high‐performance periodic real‐time applications in areas such as control systems, autonomous robots and financial systems. This article presents a novel algorithm, called Notional Approximation for Balancing Load Residues (NABLR), for scheduling these applications on high‐performance computing resources. The algorithm utilizes a combination of task residual loads and runtime laxities to carefully plan task execution between two consecutive job arrivals, so that available resources can be fully utilized and avoid deadline misses as possible. The empirical study in our article presented at the 2011 International Conference on High Performance Computing and Simulation (HPCS) was further extended by including additional static task sets and a new adaptive task set generated by our motivating application in brain–machine interfaces, which simulates the control of movement of a prosthetic limb according to activities of input signals. Out of 25,000 task sets, NABLR can schedule up to 76% of the sets versus 43% by the best known efficient algorithm (named anticipating slack earliest deadline first until zero laxity [ASEDZL]), while incurring significantly smaller overheads than those of a known optimal algorithm (on average, 80% fewer preemptions, migrations, and 75% fewer scheduler invocations), and being comparable to those of suboptimal schedulers (within only 12% more preemptions/migrations). Additionally, the evaluation results show that NABLR completes more task instances when compared with ASEDZL, which yields a greater system output accuracy. Copyright © 2012 John Wiley & Sons, Ltd.

The increasing use of online social networks (OSNs) in emergency situations shows us a promising future of human cooperation through OSNs. Despite this intense interest, a number of fundamental limitations still exist, such as lack of appropriate conceptual models and limitations on cooperation meth

Crowdsourcing can be a cost-effective method for tackling the problem of digitizing historical bio collections data, and a number of crowd sourcing platforms have been developed to facilitate interaction with the public and to design simple "Human Intelligence Tasks". However, the problem of reaching consensus on the response of the crowd is still challenging for tasks for which a simple majority vote is inadequate. This paper (a) describes the challenges faced when trying to reach consensus on data transcribed by different workers, (b) offers consensus algorithms for textual data and a consensus-based controller to assign a dynamic number of workers per task, and (c) proposes further enhancements of future crowd sourcing tasks in order to minimize the need for complex consensus algorithms. Experiments using the proposed algorithms show up to a 45-fold increase in ability to reach consensus when compared to majority voting using exact string matching. In addition, the controller is able to decrease the crowd sourcing cost by 55% when compared to a strategy that uses a fixed number of workers.

A Mixture-of-Experts (MoE) system generates an output in each operating cycle by combining results of multiple models (the “experts”). The contribution of any given expert to a final solution depends on a parameter called responsibility, which can vary from cycle to cycle. When resources are insufficient to run all experts, two problems arise: 1) how much utilization is to be allocated to experts and 2) how can a schedule be created based on these allocations. Problem (1) can be formulated as a succession of optimization problems, each of which calculates experts’ allocations in a cycle. Explicit mappings from responsibilities to allocation weights are needed to solve each of these problems in every cycle using a technique called “task compression (TC).” We refer to this baseline approach as TT-TC. Two other proposed heuristics${\ssr TT}\hbox{-}{\ssr TC}^\ast$and TT-Top reduce TC’s execution time to${\ssr O}({\mbi{N}})$for${\mbi{N}}$experts. To address (2), the proposed EPOC scheduler converts the heuristics’ allocations into schedules that satisfy capacity, execution, and learning constraints across cycles. Simulations demonstrate that our approaches enable real-time computation and significantly decrease the average percentage error of limited-resource outputs (i.e., 0.2%–40% and 0.3%–0.5% when scheduled with${\ssr TT}\hbox{-}{\ssr TC}^\ast$and TT-Top, respectively, versus 0.2%–97% when using TT-TC).

A core mission of the Integrated Digitized Biocollections (iDigBio) project is the building and deployment of a cloud computing environment customized to support the digitization workflow and integration of data from all U.S. non-federal biocollections. iDigBio chose to use cloud computing technologies to deliver a cyber infrastructure that is flexible, agile, resilient, and scalable to meet the needs of the biodiversity community. In this context, this paper describes the integration of open source cloud middleware, applications, and third party services using standard formats, protocols, and services. In addition, this paper demonstrates the value of the digitized information from collections in a broader scenario involving multiple disciplines.

Virtualized IT infrastructures combined with virtual machine migration technologies have a potential to support IT services that are resilient to partial physical infrastructure failures caused by extreme events. This paper experimentally evaluates the migration of multiple VMs across long geographical distances - an activity that is required to move virtualized IT systems from a disaster site to a safe location. Taking into account the resource availability parameters observed after the Great East Japan Earthquake, experimental results show that if (1) service downtime in the order of minutes is acceptable, (2) VMs can be kept with small storage footprint, and (3) power and network are available for tens of minutes, it is possible to migrate tens of VMs from damaged sites to a very distant stable location.

Map-Reduce has become an important paradigm for data-intensive computations. The ability to estimate Map-reduce application performance is critical for efficient resource scheduling and provisioning both on dedicated clusters and on the cloud. Current state-of-the-art techniques for performance prediction of Map- Reduce applications use analytical and simulation-based models. In this paper, we make the case for performance prediction using regression techniques based on machine-learning. Through modeling the Map-Reduce environment as a grey-box, we can leverage a combination of externally observed system features and information about sub-system internals. We identify four learning techniques with high prediction accuracy through a detailed comparative study of twenty methods. The powerful capabilities of data analytics platforms are usually accompanied by frequent faults that occur due to scale, complexity and the use of commercial off- the-shelf components. We show that our proposed approach can effectively predict degraded performance under these faulty conditions by the inclusion of additional fault-related input features. A mean prediction error of <;12% was achieved across the range of parameters studied on a 64-node Xen virtualized environment running an open-source Map-Reduce implementation, Hadoop.

The hosting of databases on virtual machines (VMs) has great potential to improve the efficiency of resource utilization and the ease of deployment of database systems. This paper considers the problem of on-demand allocation of resources to a VM running a database serving dynamic and complex query workloads while meeting QoS (Quality of Service) requirements. An autonomic resource-management approach is proposed to address this problem. It uses adaptive fuzzy modeling to capture the behavior of a VM hosting a database with dynamically changing workloads and to predict its multi-type resource needs. A prototype of the proposed approach is implemented on Xen-based VMs and evaluated using workloads based on TPC-H and RUBiS. The results demonstrate that CPU and disk I/O bandwidth can be efficiently allocated to database VMs serving workloads with dynamically changing intensity and composition while meeting QoS targets. For TPC-H-based experiments, the resulting throughput is within 89.5-100% of what would be obtained using resource allocation based on peak loads, For RUBiS, the response time target (set based on the performance under peak-load-based allocation) is met for 97% of the time. Moreover, substantial resources are saved (about 62.6% of CPU and 76.5% of disk I/O bandwidth) in comparison to peak-load-based allocation.

This paper presents a novel online scheduling algorithm for scheduling real-time adaptive systems in which tasks may have distinct resource requirements for each of thesystems' operating modes. Apart from prior work that considers only step-wise adaptation of tasks' resource utilization during mode transition, the proposed algorithm (named EAGLE-T)enables tasks to adapt their resource utilization progressively from one mode to another in a timely manner without causing any deadline miss. The upper bound of the delay and the drift between resource utilization achieved by EAGLE-T and the ideal scheduler during mode transition are provided. Performance evaluation shows that the progressive adaptation of EAGLE-Toffers improved performance over a step-wise approach (average maximal-utilization drift and mode-transition delay are reduced by up to 68.75% and 32.16%, respectively). As the probability of a mode change or the number of tasks vary, empirical results show that the resource utilization achieved by tasks scheduled using EAGLE-T is within 56% to 90% of the desired utilization(compared to 11%-81% when the step-wise scheme is used).

Summary form only given. The growing number of announced commercial and scientific clouds strongly suggests that in the near future these providers will be differentiated according to the types of their services, their cost, availability and quality. Users will be able to use these and other criteria to determine which clouds best suit their needs, a plausible scenario being the case when users need to aggregate capabilities provided by different clouds. In such scenarios it will be essential to provide virtual networking technologies that enable providers to support cross-cloud communication and users to deploy cross-cloud applications. This talk will describe one such technology, its salient features and remaining challenges. It will also put forward the idea of virtual clouds, i.e. providers of computing services overlaid on more than one cloud. A virtual cloud spans across multiple cloud providers and presents the view of a single logical cloud. Virtual clouds would enable high-level computing services to be provided by third parties who do not own physical resources, could be short or long-lived and highly dynamic. Enabling technologies, challenges and examples of sky computing will be presented.

Most data centers, clouds and grids consist of multiple generations of computing systems, each with different performance profiles, posing a challenge to job schedulers in achieving the best usage of the infrastructure. A useful piece of information for scheduling jobs, typically not available, is the extent to which applications will use available resources once they are executed. This paper comparatively assesses the suitability of several machine learning techniques for predicting spatio temporal utilization of resources by applications. Modern machine learning techniques able to handle large number of attributes are used, taking into account application- and system-specific attributes (e.g., CPU micro architecture, size and speed of memory and storage, input data characteristics and input parameters). The work also extends an existing classification tree algorithm, called Predicting Query Runtime (PQR), to the regression problem by allowing the leaves of the tree to select the best regression method for each collection of data on leaves. The new method (PQR2) yields the best average percentage error, predicting execution time, memory and disk consumption for two bioinformatics applications, BLAST and RAxML, deployed on scenarios that differ in system and usage. In specific scenarios where usage is a non-linear function of system and application attributes, certain configurations of two other machine learning algorithms, Support Vector Machine and k-nearest neighbors, also yield competitive results. In addition, experiments show that the inclusion of system performance and application-specific attributes also improves the performance of machine learning algorithms investigated.

In self-caring IT systems, faults are handled proactively, e.g. by slowing down the deterioration of system health thereby effectively avoiding or delaying system failures. This requires health management which entails health monitoring, diagnosis, prognosis, planning of recovery and remediation actions. A brief overview of our prior work, which proposes a general methodology to capture system properties and incorporate health management using Petri nets, is provided. We describe in detail an application of the proposed formal method to the design and development of middleware that can manage the health of a batch-based, job submission system on a virtualized platform. First, we describe how a real world job submission IT system is converted to a Petri net model. Secondly, we show system validation and analysis using this model to understand resource needs of different activities in the IT chain. Thirdly, we describe how the executable model is used as a system manager to control operation and health management of a virtualized test bed. Fourthly, we illustrate the use of a feedback controller to manage health deterioration due to resource depletion in the job-execution stage of the modeled IT chain. Using a proof-of-concept implementation, we show that the early detection and handling of health deteriorations results in significant benefits in terms of cost savings and down time reduction. Experimental results show that our health management framework can be used to effectively prevent job failures, while imposing low overhead to the managed system. We have shown that for a typical workload consisting of jobs that suffer from potential resource depletion faults, our feedback controller can be used to gain useful life that is needed for critical planning and remediation actions in up to 82% of the jobs.

This paper describes the design and implementation of an improved version (2.0) of a computational cyberinfrastructure for neuroscience research, called CyberWorkstation (CW). CW can provide to neurophysiology laboratories the following: (1) data storage for large volumes of neural signals, experime

The trend towards multi-/many- core design has made network-on-chip (NoC) a crucial component of future microprocessors. With CMOS processing technologies continuously scaling down to the nanometer regime, effects such as process variation (PV) and negative bias temperature instability (NBTI) significantly decrease hardware reliability and lifetime. Therefore, it is imperative for multi-core architects to consider and mitigate these effects in NoCs implemented using small-scale processing technology. This paper reports on a first step to optimize NoC architecture reliability in light of both PV and NBTI effects. We propose novel techniques that can hierarchically alleviate PV and NBTI effects on NoC while leveraging their benign interaction. Our low-level design improves PV and NBTI efficiency of key components (e.g. virtual channel allocation logics, virtual channels) of critical paths of the pipelined router microarchitecture. Our high-level mechanisms leverage NBTI degradation and PV information from multiple routers to intelligently route packets, delivering optimized performance-power-reliability across the NoC substrate. Experimental results show that our intra-router level techniques (i.e. VA_M1 and VC_M2) reduce guardband by 47% while improving network throughput by 24%. Our inter-router optimization scheme (i.e. IR_M3) results in 50% guardband reduction and 19% network latency improvement.

Mixture-of-Experts (MoE) systems solve intricate problems by combining results generated independently by multiple computational models (the "experts"). Given an instance of a problem, the responsibility of an expert measures the degree to which the expert's output contributes to the final solution. Brain Machine Interfaces are examples of applications where an MoE system needs to run periodically and expert responsibilities can vary across execution cycles. When resources are insufficient to run all experts in every cycle, it becomes necessary to execute the most responsible experts within each cycle. The problem of adaptively scheduling experts with dynamic responsibilities can be formulated as a succession of optimization problems. Each of these problems can be solved by a known technique called "task compression" using explicit mappings described in this paper to relate expert responsibilities to task elasticities. A novel heuristic is proposed to enable real-time execution rate adaptation in MoE systems with insufficient resources. In any given cycle, the heuristic uses sensitivity analysis to test whether one of two pre-computed schedules is the optimal solution of the optimization problem to avoid re-optimization when the test result is positive. These two candidate schedules are the schedule used in the previous cycle and the schedule pre-computed by the heuristic during the previous cycle, using future responsibilities predicted by the heuristic's responsibility predictor. Our heuristic significantly reduces the scheduling delay in the execution of experts when re-execution of the task-compression algorithm is not needed from O(N2) time, where N denotes the number of experts, to O(N) time. Experimental evaluation of the heuristic on a test case in motor control shows that these time savings occur and scheduled experts' deadlines are met in up to 90% of all cycles. For the test scenario considered in the paper, the average output error of a real-time MoE system due to the use of limited resources is less than 7%.

This paper describes the architecture and implementation of a Java-based appliance for collaborative review of crashes involving injured children in order to determine mechanisms of injury. The multidisciplinary expertise needed for such reviews is not available at any one institution, resulting in

With the emergence of multiple cloud providers of Infrastructure-as-a-Service, it becomes possible to envision a near-future when high-performance computing users could combine services from different clouds to access huge numbers of resources. However, as more administrative privileges are exposed to end users, providers are required to deploy network security measures that present challenges to the network virtualization technologies that are needed to enable inter-cloud communication. This paper studies these challenges and proposes techniques to enable unmodified applications on resources across distinct clouds. The techniques are implemented in TinyViNe, an extension to ViNe, a virtual networking technology for distributed resources in different administrative domains. The results of evaluating TinyViNe on a WAN-based testbed across three sites are reported for a bioinformatics application (BLAST) and MPI benchmarks. The results confirm that TinyViNe enables cross-cloud computing while having little impact on application performance. TinyViNe also has auto-configuration and ¿download-and-run¿ capabilities for easy deployment by users who are not knowledgeable about networking.

As transistor process technology approaches the nanometer scale, process variation significantly affects the design and optimization of high performance microprocessors. Prior studies have shown that chip operating frequency and leakage power can have large variations due to fluctuations in transistor gate length and sub-threshold voltage. In this work, we study the impact of process variation on microarchitecture soft error robustness, an increasing reliability design challenge in the billion-transistor chip era. We explore two techniques that can effectively mitigate the effect of design parameter variation while significantly enhancing microarchitecture soft error reliability. Our first technique is entry-based. It tolerates the deleterious impact of variable latency techniques on soft error reliability by reducing the quantity and residency cycle of vulnerable bits in the microarchitecture structure at a fine granularity. Our second technique is structure-based. It applies body biasing schemes to dynamically adapt transistor sub-threshold voltage (and hence device-level soft error robustness) to the program reliability characteristics at a coarse granularity. We also combine the two techniques which further produces improved results. Compared to existing process variation tolerant schemes, our proposed techniques achieve optimal trade-offs between reliability, performance, and power. To our knowledge, this paper presents the first study on characterizing and optimizing processor microarchitecture resilience to soft errors in light of process variation.

As semiconductor technology scales, reliability is becoming an increasingly crucial challenge in microprocessor design. The rSRAM and voltage scaling are two promising circuit-level radiation hardening techniques to increase soft error robustness of a SRAM-based storage cell. However, applying circuit-level radiation hardening techniques to all on-chip transistors will result in significant overhead in performance and power consumption. In this paper, we propose microarchitecture support that allows cost-effective implementation of radiation hardened key microarchitecture structures (e.g. issue queue and reorder buffer) in SMT processors using soft error robust circuit techniques. Our study shows that the combined circuit and microarchitecture techniques achieve attractive tradeoffs between reliability, performance and power.

This paper proposes and evaluates an approach to the parallelization, deployment and management of bioinformatics applications that integrates several emerging technologies for distributed computing. The proposed approach uses the MapReduce paradigm to parallelize tools and manage their execution, machine virtualization to encapsulate their execution environments and commonly used data sets into flexibly deployable virtual machines, and network virtualization to connect resources behind firewalls/NATs while preserving the necessary performance and the communication environment. An implementation of this approach is described and used to demonstrate and evaluate the proposed approach. The implementation integrates Hadoop, Virtual Workspaces, and ViNe as the MapReduce, virtual machine and virtual network technologies, respectively, to deploy the commonly used bioinformatics tool NCBI BLAST on a WAN-based test bed consisting of clusters at two distinct locations, the University of Florida and the University of Chicago. This WAN-based implementation, called CloudBLAST, was evaluated against both non-virtualized and LAN-based implementations in order to assess the overheads of machine and network virtualization, which were shown to be insignificant. To compare the proposed approach against an MPI-based solution, CloudBLAST performance was experimentally contrasted against the publicly available mpiBLAST on the same WAN-based test bed. Both versions demonstrated performance gains as the number of available processors increased, with CloudBLAST delivering speedups of 57 against 52.4 of MPI version, when 64 processors on 2 sites were used. The results encourage the use of the proposed approach for the execution of large-scale bioinformatics applications on emerging distributed environments that provide access to computing resources as a service.

Connectivity limitations of the current Internet pose challenges to e-Science infrastructure, as communication between resources is of key importance for the sharing of hardware, software and data across geographically distributed institutions. To overcome such limitations many overlay networks have been developed. Existing solutions report performance that can keep up with slow wide-area links - however the question remains as to how overlay networks perform on new high-speed Internet connections. This paper characterizes the performance of user-level packet processing, which is at the core of most overlay networks implementations. To this end, building blocks of packet processing software are identified and characterized, and performance of IP forwarders developed in C and Java are compared through extensive measurements. Factors that affect the performance of overlay networks and limitations of existing solutions are characterized, providing insights on possible improvements. Experimental results show the following: to achieve maximum throughput, only a few microseconds (2 to 5) can be spent in virtual network processing; processing of small packets can limit TCP throughput; and overlays need to be carefully architected as encapsulation overheads can be substantial.

The issue queue (IQ) is a key microarchitecture structure for exploiting instruction-level and thread-level parallelism in dynamically scheduled simultaneous multithreaded (SMT) processors. However, exploiting more parallelism yields high susceptibility to transient faults on a conventional IQ. With the rapidly increasing soft error rates, the IQ is likely to be a reliability hot-spot on SMT processors fabricated with advanced technology nodes using smaller and denser transistors with lower threshold voltages and tighter noise margins. In this paper, we explore microarchitecture techniques to optimize IQ reliability to soft error on SMT architectures. We propose to use off-line instruction vulnerability profiling to identify reliability critical instructions. The gathered information is then used to guide reliability-aware instruction scheduling and resource allocation in multithreaded execution environments. We evaluate the efficiency of the proposed schemes across various SMT workload mixes. Extensive simulation results show that, on average, our microarchitecture level soft error mitigation techniques can significantly reduce IQ vulnerability by 42% with 1% performance improvement. To maintain runtime IQ reliability for pre-defined thresholds, we propose dynamic vulnerability management (DVM) mechanisms. Experimental results show that our DVM techniques can effectively achieve desired reliability/performance tradeoffs.

Negative bias temperature instability (NBTI), which reduces the lifetime of PMOS transistors, is becoming a growing reliability concern for sub-micrometer CMOS technologies. Parametric variation introduced by nano-scale device fabrication inaccuracy can exacerbate the PMOS transistor wear-out problem and further reduce the reliable lifetime of microprocessors. In this work, we propose microarchitecture design techniques to combat the combined effect of NBTI and process variation (PV) on the reliability of high-performance microprocessors. Experimental evaluation shows our proposed process variation aware (PV-aware) NBTI tolerant microarchitecture design techniques can considerably improve the lifetime of reliability operation while achieving an attractive trade-off with performance and power.

With the advance of semiconductor processing technology, soft errors have become an increasing cause of failures of microprocessors fabricated using smaller and more densely integrated transistors with lower threshold voltages and tighter noise margins. With diminishing performance returns on wider issue superscalar processors, the microprocessor design industry has opted for using simultaneous multithreaded (SMT) architectures in commercial processors to exploit thread-level parallelism (TLP). SMT techniques enhance overall system performance but also introduce greater susceptibility to soft errors - concurrently executing multiple threads exposes many program runtime states to soft-error strikes at any given time. The issue queue (IQ) is a key micro architecture structure to exploit instruction-level and thread-level parallelism. On SMT processors, the IQ buffers a large number of instructions from multiple threads and is more susceptible to soft-error strikes. In this paper, we explore the use of operand-readiness-based instruction dispatch (ORBIT) as an effective mechanism to mitigate IQ soft-error vulnerability on SMT processors. We observe that IQ soft-error vulnerability is largely affected by instructions waiting for their source operands. The overall IQ soft-error vulnerability can be effectively reduced by minimizing the number of waiting instructions and their residency cycles in the IQ. We develop six techniques that aim to improve IQ reliability with negligible performance degradation on SMT processors. Moreover, we extend our techniques with prediction methods that can anticipate the readiness of source operands ahead of time. The ORBIT schemes integrated with reliability-awareness and readiness prediction achieve more attractive reliability/performance trade-offs. The best of the proposed schemes (e.g. Predict_DelayACE) reduces IQ vulnerability by 79% with only 1% throughput IPC and 3% harmonic IPC reduction across all studied workloads.

Semiconductor transient faults (i.e. soft errors) have become an increasingly important threat to microprocessor reliability. Simultaneous multithreaded (SMT) architectures exploit thread-level parallelism to improve overall processor throughput. A great amount of research has been conducted in the past to investigate performance and power issues of SMT architectures. Nevertheless, the effect of multithreaded execution on a microarchitecture's vulnerability to soft error remains largely unexplored. To address this issue, we have developed a microarchitecture level soft error vulnerability analysis framework for SMT architectures. Using a mixed set of SPEC CPU 2000 benchmarks, we quantify the impact of multithreading on a wide range of microarchitecture structures. We examine how the baseline SMT microarchitecture reliability profile varies with workload behavior, the number of threads and fetch policies. Our experimental results show that the overall vulnerability rises in multithreading architectures, while each individual thread shows less vulnerability. By considering both performance and reliability, SMT outperforms superscalar architectures. The SMT reliability and its tradeoff with performance vary across different fetch policies. With a detailed analysis of the experimental results, we point out a set of potential opportunities to reduce SMT microarchitecture vulnerability, which can serve as guidance to exploiting thread-aware reliability optimization techniques in the near future. To our knowledge, this paper presents the first effort to characterize microarchitecture vulnerability to soft error on SMT processors

Abstract Science gateways require the easy enabling of legacy scientific applications on computing Grids and the generation of user‐friendly interfaces that hide the complexity of the Grid from the user. This paper presents the In‐VIGO approach to the creation and management of science gateways. First, we discuss the virtualization of machines, networks and data to facilitate the dynamic creation of secure execution environments that meet application requirements. Then we discuss the virtualization of applications, i.e. the execution on shared resources of multiple isolated application instances with customized behavior, in the context of In‐VIGO. A Virtual Application Service (VAS) architecture for automatically generating, customizing, deploying, and using virtual applications as Grid services is then described. Starting with a grammar‐based description of the command‐line syntax, the automated process generates the VAS description and the VAS implementation (code for application encapsulation and data binding) that is deployed and made available through a Web interface. A VAS can be customized on a per‐user basis by restricting the capabilities of the original application or by adding to it features such as parameter sweeping. This is a scalable approach to the integration of scientific applications as services into Grids and can be applied to any tool with an arbitrarily complex command‐line syntax. Copyright © 2006 John Wiley & Sons, Ltd.

Summary form only given. Heterogeneity in computing systems has been driven by, among others, one or more of the following factors: need for better performance (e.g. in multi-core chips), applications' requirements (e.g. in digital processing systems), timing and logistics of computer facility development (e.g. clusters that are extended and upgraded over time) and emergent systems of systems (e.g. for grid-computing). The premise that these heterogeneous computing systems (HCSs) offer cost and performance benefits is true only if they can be efficiently programmed. The perspectives and questions on programming HCSs considered by this panel include the following: 1) Should programmers be exposed to heterogeneity so that they can squeeze all the necessary performance by taking advantage of the best resources for the jobs that need them? How can we handle the glut of programmers wishing to program such complex and extensive systems? 2) Should we design compilers that schedule and optimize programs written for homogeneous systems for execution on heterogeneous systems? Will the resulting programs run with better performance than they could achieve in a homogeneous system? How should better be defined in this context? 3) Are programming languages irrelevant in the sense that one can always connect components and/or services to accomplish any task? How generally applicable is this programming model? 4) Are HCS's inherently distributed memory entities where shared-memory programming models cannot succeed? Can shared- and distributed-memory models coexist? How do currently available languages fare in this regard?

This paper describes a virtual networking approach for grids called ViNe. It enables symmetric connectivity among grid resources and allows existing applications to run unmodified. Novel features of the ViNe architecture include: easy virtual networking administration; support for physical private networks and support for multiple independent virtual networks in the same infrastructure. The requirements of an application-friendly virtual network environment are presented and it is shown how the proposed solution meets them. Qualitative arguments are provided to justify all design decisions. Also presented is an experimental evaluation of the round-trip latencies and bandwidths achieved by a reference implementation. Measurements are reported for WAN-scenarios involving three different institutions. Under favorable conditions, ViNe bandwidths are within 90 to 100% of the available physical network bandwidth

Computer systems increasingly depend on exploiting program dynamic behavior to optimize performance, power and reliability. Prior studies have shown that program execution exhibits phase behavior in both performance and power domains. Reliabilityoriented program phase behavior, however, remains largely unexplored. As semiconductor transient faults (soft errors) emerge as a critical challenge to reliable system design, characterizing program phase behavior from a reliability perspective is crucial in order to apply dynamic fault-tolerant mechanisms and to optimize performance/reliability trade-offs. In this paper, we compute run-time program vulnerability to soft errors on four microarchitecture structures (i.e. instruction window, reorder buffer, function units and wakeup table) in a high-performance out-of-order execution superscalar processor. Experimental results on the SPEC2000 benchmarks show a considerable amount of time varying behavior in reliability measurements. Our study shows that a single performance metric, such as IPC, cache miss or branch misprediction, is not a good indicator for program vulnerability. The vulnerabilities of the studied microarchitecture structures are then correlated with program code-structure and run-time events to identify vulnerability phase behavior. We observed that both program code-structure and run-time events appear promising in classifying program reliability phase behavior. Overall, performance counter based schemes achieved an average Coefficient of Variation (COV) of 3.5%, 4.5%, 4.3% and 5.7% on the instruction queue, reorder buffer, function units and the wakeup table, while basic block vectors offer COVs of 4.9%, 5.8%, 5.4% and 6% on the four studied microarchitecture structures respectively. We found that in general, tracking performance metrics performs better than tracking control flow in identifying reliability phase behavior of applications. To our knowledge, this paper is the first to characterize program reliability phase behavior at the microarchitecture level.

This paper is concerned with faults, error bounds and reliability modeling of nanotechnology-based circuits. First, we briefly review failure mechanisms and fault models in nanoelectronics. Second, reliability functions based on probabilistic models are developed for unreliable logic gates. We then show that fundamental gate error bounds for general probabilistic computation can be derived using the nonlinear mapping functions constructed from the gate models. Finally, an analytical approach is proposed for estimating reliabilities of nanoelectronic circuits. This approach is based on the probabilistic modeling of unreliable logic gates and interconnects. In spite of the approximations used in probabilistic modeling, our study suggests that the proposed approach provides a simple and efficient way to model the reliability of nanoelectronic circuits.

To best exploit the potential of the grid, it is necessary to "grid-enable" legacy applications that were not originally developed to run on a grid. In this paper, a generic framework to grid-enable legacy applications is presented. In particular, this paper focuses on a general approach to model and represent an application in a way that is supportive of the key properties of the grid-enabling framework: generality, automatic generation and integration of grid applications, plug-and-play deployment, and interoperability. Based on the model, a configuration language is developed to describe a wide range of command-line applications and their execution requirements. It is easy to use and does not require the application enabler to know the details of the grid middleware. A case study is presented to illustrate the automated grid-enabling of a legacy application in In-VIGO (in-virtual information grid organizations), a grid computing infrastructure that makes extensive use of visualization technology

This poster briefly introduces two resource-virtualization techniques needed for the creation of virtual(ized) grids: virtual networks and virtual application services. The former provides bidirectional network connectivity even in the presence of firewalls, network address translation gateways and proxies by creating virtual routers and virtual IP space. The later allows automated creation and deployment of legacy applications into grids by generating a virtual application service that allows the execution in shared resources of multiple isolated application instances with customized behavior.

This paper describes a scalable approach to the enabling of legacy scientific applications on computing grids using a service-oriented architecture. In the context of this paper grid-enabling means turning an existing application, installed on a grid resource, into a service and generating the application-specific user interfaces to use that application through a Web portal. Scalability is achieved by providing a common abstraction for a category of applications and providing a "generic" application service to wrap those applications as services. The focus of this paper's approach is on grid-enabling "command-oriented" scientific applications. The novel aspect of the approach is that the entire process -from turning an application into a service to the user-interface generation for that application - is done automatically, without requiring coding or grid-system downtime. Portlet technology is used to dynamically generate application-specific interfaces. Further, the approach makes it possible to customize the applications for different user groups by way of simplifying, restricting or composing the functionalities of applications. The approach is useful for building grid portals on which a large number of applications need to be dynamically enabled.

The exponential growth in the amount of genomic information has spurred growing interest in large scale analysis of genetic data. Bioinformatics applications represent the increasingly important workloads. However, very few results on the behavior of these applications running on the state-of-the-art microprocessor and systems have been published. This paper proposes a suite of widely used bioinformatics applications and studies the execution characteristics of these benchmarks on a representative architecture-the Intel Pentium 4. To understand the impacts and implications of bioinformatics workloads on the microprocessor designs, we contrast the characteristics of bioinformatics workloads and the widely used SPEC 2000 integer benchmarks.

The operational principles, components, and organization of a Grid-computing infrastructure called In-VIGO (standing for In Virtual Information Grid Organizations)are described. In-VIGO enables computational engineering and science in virtual information Grid organizations. Its distinctive feature is the extensive use of virtualization technologies to provide secure execution environments as needed by tools and users. This paper reviews and motivates the requirements of a cyber infrastructure for computational nanoelectronics. It then explains how such requirements are addressed by the In-VIGO middleware approach, which uses virtualized resources to build computational Grids. The architecture and key design aspects of its first deployed version-In-VIGO 1.0-are presented. It is operational and currently being used to enable the use of computational electronics tools over the Web. Aspects of the design and architecture of the next version of In-VIGO are also presented. It uses Web services standards and components, and lessons learned from In-VIGO 1.0.

In modern architectures, memory access latency is an increasingly performance-limiting factor. To reduce this latency, we propose concepts and implementation of a new technique that uses an in-memory processor to precompute future, critical load addresses and forward the computed values to the main processor. The acronym for this technique is IMPT for In-Memory Precomputation-based forwarding Threads. IMPT combines the advantages of precomputation-based techniques with the low memory access latency of processing-in-memory. To evaluate IMPT, we use a cycle-accurate simulation of an aggressive out-of-order processor with accurate simulation of bus and memory contention. The results show a performance gain of up to 1.47 (1.21 on average) over an aggressive superscalar processor. The average load access latency decreases by up to 55% (32% on average).

Summary form only given. Single sign-on (SSO) is an essential desired feature of computational grids. Its implementation is challenging because resources cross administrative domains and are managed by heterogeneous access schemes. We present an approach for single sign-on in a deployed functioning grid called In-VIGO. The approach relies on decoupling grid user accounts from local user accounts and making use of role-based access control lists. Role-based accesses via delegation mechanisms using short-lived user identities enable In-VIGO to handle interactive applications and application-specific authentication mechanisms. This capability is not present in existing grid architectures. SSO implementations for usage scenarios in In-VIGO are described to highlight the applicability of the proposed approach. In particular, access to interactive applications with their own security mechanisms, such as VNC, and access to remote data can be achieved using proxies that delegate In-VIGO user access via short-lived user identities.

Virtual machines provide flexible, powerful execution environments for Grid computing, offering isolation and security mechanisms complementary to operating systems, customization and encapsulation of entire application environments, and support for legacy applications. This paper describes a Grid service — VMPlant — that provides for automated configuration and creation of flexible VMs that, once configured to meet application needs, can then subsequently be copied ("cloned") and dynamically instantiated to provide homogeneous execution environments across distributed Grid resources. In combination with complementary middleware for user, data and resource management, the functionality enabled by VMPlant allows for problem-solving environments to deliver Grid applications to users with unprecedented flexibility. VMPlant supports a graph-based model for the definition of customized VM configuration actions; partial graph matching, VM state storage and "cloning" for efficient creation. This paper presents the VMPlant architecture, describes a prototype implementation of the service, and presents an analysis of its performance.

We advocate a novel approach to grid computing that is based on a combination of "classic" operating system level virtual machines (VMs) and middleware mechanisms to manage VMs in a distributed environment. The abstraction is that of dynamically instantiated and mobile VMs that are a combination of traditional OS processes (the VM monitors) and files (the VM state). We give qualitative arguments that justify our approach in terms of security, isolation, customization, legacy support and resource control, and we show quantitative results that demonstrate the feasibility of our approach front a performance perspective. Finally, we describe the middleware challenges implied by the approach and an architecture for grid computing using virtual machines.

A modular mapping consists of a linear transformation followed by modulo operations. It is characterized by a transformation matrix and a vector of moduli, called the modulus vector. Modular mappings are useful to derive parallel versions of algorithms with commutative operations and algorithms intended for execution on processor arrays with toroidal networks. In order to preserve algorithm correctness, modular mappings must be injective. Results of previous work characterize injective modular mappings of rectangular index sets. This paper provides a technique to generate modular mappings that satisfy these injective conditions and extends the results to general index sets. For an n-dimensional rectangular index set, the technique has O(n/sup 2/n!) complexity. To facilitate generation of efficient code, modular mappings must also be reversible (i.e., have easily described inverses). An O(n/sup 2/) method is provided to generate reversible modular mappings. This method reduces the search space by fixing entries of the modulus vector while attempting to minimize the number of entries to exclude few solutions. For general index sets defined by linear inequalities, injectivity can be checked by formulating and solving a set of linear inequalities. A modified Fourier-Motzkin elimination is proposed to solve these inequalities. To generate an injective modular mapping of an index set defined by linear inequalities, this paper proposes a technique that attempts to minimize the values of the entries of the modulus vector. Several examples are provided to illustrate the application of the above mentioned methods, including the case of BLAS routines.

The push to obtain smaller and denser circuits solely based on lithography and silicon technology is quickly reaching limits imposed by device physics and processing technology. It is anticipated that these limits will invalidate Moore's law and lead to unacceptable manufacturing costs, unreliable devices, and hard-to-manage power dissipation and interconnect problems. Nanotechnologies that rely on self-assembly, biomolecular components, and nanoelectronics are promising alternatives to silicon-based microelectronics. They will eventually enable levels of integration that exceed that of today's silicon-based microelectronics by three orders of magnitude. These nascent technologies present intriguing challenges and exciting opportunities to use biologically inspired solutions to address system architecture questions. This paper discusses recent results of an ongoing collaborative research effort by nanotechnologists, neurocomputing experts, and computer and circuit designers to explore novel architectures for nanoscale neuromorphic systems. The focus is placed on implementations whose behavior depends on how propagation delays affect communication among system components. The components under consideration are reminiscent of spiking neurons and, unlike in classical systems, interconnect is used for computation as well as communication purposes. Hybrid systems are also briefly discussed.

In this paper, an online heuristic is proposed and evaluated, for managing the dynamic memory in a computer system with active disks, by physically colocating in disk memory or main memory, the data pages being accessed by a computation slice. This enables a runtime system that can offload the corresponding computation slice to the appropriate processing unit at the disk memory or main memory. A modified version of SEQUITUR, an online compression algorithm, is used to identify the affinity among sets of pages in a virtual memory page reference stream, and a page allocation and replacement policy is presented. The sets of pages identified are shown to closely match the sets of pages referenced by computation slices, using a suite of data access kernels as benchmarks. The paging policy is evaluated with page traces of micro benchmarks and real applications. In memory constrained environments, with additional memory at the disk, most of the benchmarks see improved performance, due to fewer page faults. The paging heuristic can colocate 50% of the affinity sets on average and can offload up to 100% of the computation to disk.

Describes a virtual file system that allows data to be transferred on demand between storage and computational servers for the duration of a computing session. The solution works with unmodified applications (even commercial ones) running on standard operating systems and hardware. The virtual file system employs software proxies to broker transactions between standard NFS (Network File System) clients and servers; the proxies are dynamically configured and controlled by computational grid middleware. The approach has been implemented and extensively exercised in the context of PUNCH (Purdue University Network Computing Hubs), an operational computing portal that has more than 1,500 users across 24 countries. The results show that the virtual file system performs well in comparison to native NFS: performance analyses show that the proxy incurs mean overheads of 1% and 18% with respect to native NFS for a single-client execution of the Andrew benchmark in two representative computing environments, and that the average overhead for eight clients can be reduced to within 1% of native NFS with concurrent proxies.

This paper describes a novel, pipelined resource management architecture for computational grids. The design is based on two key realizations. One is that resource management involves a sequence of tasks that is best handled by a pipeline. As shown in the paper, this approach results in a scalable architecture for decentralized scheduling. The other realization is that static aggregation of resources for improved scheduling is inadequate in wide-area computing environments because the needs of users and jobs change with both, location and time. The described architecture addresses this problem by dynamically aggregating resources in a manner that continuously optimizes system response. This is accomplished by way of an active yellow pages directory that allows aggregation constraints to be (re)defined on the fly. An initial prototype of the active yellow pages service has been deployed in the PUNCH network computing environment. Experiences with the production PUNCH system and preliminary results from controlled experiments indicate that the active yellow pages service performs well.

Data dependence speculation allows a compiler to relax the constraint of data-independence to issue tasks in parallel, increasing the potential for automatic extraction of parallelism from sequential programs. The paper proposes hardware mechanisms to support a data-dependence speculative distributed shared-memory (DDSM) architecture that enable speculative parallelization of programs with irregular data structures and inherent coarse-grin parallelism. Efficient support for coarse-grain tasks requires large buffers for speculative data; DDSM leverages cache and directory structures to provide large buffers that are managed transparently from applications. The proposed cache and directory extensions provide support for distributed speculative versions of cache blocks, run-time detection of dependence violations, and program-order reconciliation of cache blocks. The paper describes the DDSM architecture and presents a simulation-based evaluation of its performance on five benchmarks chosen from the Spec95 and Olden suites. The proposed system yields simulated speedups of 3.8 to 12.5 in a 16-node configuration for programs with coarse-grain speculative windows (millions of instructions and hundreds of KBytes of speculative data).

This paper elaborates on mechanisms by which users, data, and applications can bedecoupledfrom individual computers and administrative domains. The mechanisms, which consist of logical user accounts and a virtual #le system, introduce a layer of abstraction between the physical computing infrastructure and the virtual computational grid perceived by users. This abstraction converts compute servers into interchangeable parts, allowing a computational grid to assemble computing systems at run time without being limited by the traditional constraints associated with user accounts, #le systems, and administrative domains. The described approach has already been deployedinthe

This paper explores area/parallelism tradeoffs in the design of distributed shared-memory (DSM) multiprocessors built out of large single-chip computing nodes. In this context, area-efficiency arguments motivate a heterogeneous organization consisting of few nodes with large caches designed for single-thread parallelism, and a larger number of nodes with smaller caches designed for multi-thread parallelism. Quantitative performance of such organization is reported for a set of homogeneous multiprocessor programs from the SPLASH-2 benchmark suite. These programs are mapped onto the heterogeneous processors without source code modifications via static thread assignment policies. Simulation-based analysis is used to compare the performance of heterogeneous and homogeneous DSMs that occupy the same silicon area. The analysis shows that a 4-node heterogeneous DSM with 21 processors outperforms its homogeneous counterpart with 4 processors by an average age of 36% for the studied multiprocessor workload, while having the same performance for sequential codes. A sensitivity analysis based on a factorial design experiment is used to study the implications of processor, memory, and network heterogeneity on overall cost and performance of a heterogeneous DSM. The studied benchmarks are affected, on average, primarily by heterogeneity in processor performance (59.3%), followed by cache sizes (18.2%), memory latency (14.6%), and network latency (5.6%).

This paper outlines the issues that must be addressed in order to allow cluster management systems such as Condor, DQS (Distributed Queueing Service) and PBS (Portable Batch System) to be transparently used via a wide-area network computing system such as PUNCH (Purdue University Network Computing Hubs).

This paper describes the performance and interoperability issues that arise in the process of integrating cluster management systems into a wide-area network-computing environment, and provides solutions in the context of the Purdue University Network Computing Hubs (PUNCH). The described solution provides users with a single point of access to resources spread across administrative domains, and an intel ligent translation process makes it possible for users to submit jobs to different types of cluster management systems in a transparent manner. The approach does not require any modifications to the cluster management software; however, call-back and caching capabilities that would improve performance and make such systems more interoperable with wide-area computing systems are discussed.

We present a new parallel programming tool environment that is (1) accessible and executable "anytime, anywhere," through standard Web browsers and (2) integrated in that it provides tools that adhere to a common underlying methodology for parallel programming and performance tuning. The environment is based on a new network computing infrastructure, developed at Purdue University. We evaluate our environment qualitatively by comparing our tool access method with conventional schemes of software download and installation. We also quantitatively evaluate the efficiency of interactive tool access in our environment. We do this by measuring the response times of various functions of the URSA MINOR tool and compare them with those of a Java Applet-based "anytime, anywhere" tool access method. We found that our environment offers significant advantages in terms of tool accessibility, integration, and efficiency.

Traditional centralized monitoring systems do not scale to present-day large, complex, network- computing systems. Based on recent SNMP standards for distributed management, this paper addresses the scalability problem through distribution of monitoring tasks, applicable for tools such as SI- MONE (SNMP-based monitoring prototype implemented by the authors). Distribution is achieved by introducing one or more levels of a dual entity called the Intermediate Level Manager (ILM) between a manager and the agents. The ILM accepts monitoring tasks described in the form of scripts and delegated by the next higher entity. The solution is flexible and integratable into a SNMP tool without altering other system components. A testbed of up to 1024 monitoring elements is used to assess scalability. Noticeable improvements in the round trip delay (from seconds to less than tenth of a second) were observed when more than 200 monitoring elements are present and as few as 2 ILM's are used.

This paper describes and evaluates the application of three local learning algorithms-nearest-neighbor, weighted-average, and locally-weighted polynomial regression-for the prediction of run-specific resource-usage on the basis of run-time input parameters supplied to tools. A two-level knowledge base allows the learning algorithms to track short-term fluctuations in the performances of computing systems, and the use of instance editing techniques improves the scalability of the performance-modeling system. The learning algorithms assist PUNCH, a network-computing system at Purdue University, in emulating an ideal user in terms of its resource management and usage policies.

The work performed by a parallel algorithm is the product of its running time and the number of processors it requires. This paper presents work-efficient (or cost-optimal) routing algorithms to determine the switch settings for realizing permutations on rearrangeable symmetrical networks such as Benes and the reduced /spl Omega//sub N//spl Omega//sub N//sup -1/. These networks have 2n-1 stages with N=2/sup n/ inputs/outputs, each stage consisting of N/2 crossbar switches of size (2/spl times/2). Previously known parallel routing algorithms for a rearrangeable network with N inputs determine the states of all switches recursively in O(n) iterations using N processors. Each iteration determines the switch settings of at most two stages of the network and requires at least O(n) time on a computer of N processors, regardless of the type of its interconnection network. Hence, the work of any previously known parallel routing algorithm equals at least O(Nn/sup 2/) for setting up all the switches of a rearrangeable network. The new routing algorithms run on a computer of p processors, 1/spl les/p/spl les/N/n, and perform work O(Nn). Moreover, because the range of p is large, the new routing algorithms do not have to be changed in case some processors become faulty.

Many of the systems that currently allow computing on the World Wide Web target specific tools. Such solutions tend to be non-reusable in spite of the fact that they involve a significant amount of duplicated effort. This paper describes the issues involved in the design of a demand-based network-computing system, and presents an operational prototype (the Purdue University Network-Computing Hubs, or PUNCH) that allows users to access and run existing software tools via standard Web browsers. The tools do not have to be written in any particular language, and access to source code is not required. The PUNCH infrastructure can be distributed in a manner that allows tools to be (user-transparently) executed wherever they reside. Currently, PUNCH contains over 30 tools from eight universities and four vendors, and serves more than 500 users. During the past three years, PUNCH users have logged more than 860,000 hits and have performed over 54,000 simulations.

This paper reports on an application of artificial intelligence to achieve demand-based scheduling within the context of a network-computing infrastructure. The described AI system uses tool-specific, run-time input to predict the resource-usage characteristics of runs. Instance-based learning with locally weighted polynomial regression is employed because of the need to simultaneously learn multiple polynomial concepts and the fact that knowledge is acquired incrementally in this domain. An innovative use of a two-level knowledge base allows the system to account for short-term variations in compute-server and network performance and exploit temporal and spatial locality of runs. Instance editing allows the approach to be tolerant to noise and computationally feasible for extended use. The learning system was tested on three tools during normal use of the Purdue University Network Computing Hubs. Results indicate that the described instance-based learning technique using locally weighted regression with a locally linear model works well for this domain.

Many optimizations (of programs with loops) used in parallelizing compilers and systolic array design are based on linear transformations of loop iteration spaces. Additional important optimizations and designs are possible by using recently proposed modular mappings, which are described by linear transformations modulo a constant vector. Previous work on modular mappings focused an conditions that guarantee injectivity of a modular mapping for algorithms with rectangular index sets. This paper generalizes previous work by providing new injectivity conditions that cover the cases when the program index set has arbitrary shape and size, and the target processor array and the mapping moduli are of arbitrary size. A systematic technique to efficiently generate modular mappings is also proposed. The complexity of the proposed generation technique is O(n/sup 2/n!) for a nested loop of depth n with a rectangular index set and a target processor array with as many processors as required. A bounded search scheme is also provided for general cases. Each trial is formulated as an integer linear programming problem with at most 3n variables.

In this paper, a modified version of previously proposed quasi-barrier technique is developed. On distributed memory machines, relaxation with modified quasi-barriers can be used to perform basis computations that arise in symbolic polynomial manipulation. In this type of synchronous computation, the set of tasks is distributed across the processors. Each nonzero result of a task reduction dynamically generates a set of new tasks. The distribution of these newly generated tasks can have a significant impact on the overall execution time of the parallel computation. In this paper, four task distribution strategies, named modified block, modified sorted block, modified cyclic, and modified sorted cyclic are developed and their performances are comparatively evaluated. For the experiments performed on an 18-node IBM SP2, the modified cyclic distribution provides the best performance overall.

Article Generalized Cannon's algorithm for parallel matrix multiplication Share on Authors: Hyuk-Jae Lee Department of Computer Science, Louisiana Tech University, Ruston, LA Department of Computer Science, Louisiana Tech University, Ruston, LAView Profile , James P. Robertson School of Electrical and Computer Engineering, Purdue University, W. Lafayette, IN School of Electrical and Computer Engineering, Purdue University, W. Lafayette, INView Profile , José A. B. Fortes School of Electrical and Computer Engineering, Purdue University, W. Lafayette, IN School of Electrical and Computer Engineering, Purdue University, W. Lafayette, INView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 44–51https://doi.org/10.1145/263580.263591Online:11 July 1997Publication History 19citation2,818DownloadsMetricsTotal Citations19Total Downloads2,818Last 12 Months46Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Data alignment and computation domain partitioning techniques have been widely investigated to reduce communication overheads in distributed memory systems. This paper considers how these two techniques can be combined and applied to affine nested loops. Current data alignment techniques focus on individual entries of data arrays and, in general, cannot be used directly for cases when blocks of entries should be aligned collectively. This paper shows that existing data alignment techniques can be applied to partitioned algorithms if the null space of the data array indexing matrix is a boundary of computation blocks or the intersection of some computation block boundaries. These conditions can be used to generate several different partitionings and time–space transformations for a given target architecture. An example illustrates how it is possible to trade-off the number of communications and the memory space. Another example shows partitions of matrix–matrix multiplication that have smaller communication–computation ratios than Cannon's algorithm.

Modular mappings have been recently proposed for optimization of algorithms that cannot be efficiently mapped by affine mappings. This paper addresses the problem of generating modular mappings that satisfy conditions for validity and optimality. In general, this is a difficult problem due to the presence of non-linear constraints. Hence, a method of O(n/sup 2/) complexity is provided to assign values to some entries of a transformation matrix so that non-linear constraints are transformed into linear ones, where n is the dimension of a computation domain. The proposed heuristic attempts to reduce the number of value-assigned entries and exclude as few solutions as possible. This paper also considers the issue of deriving the inverse transformation of a given modular mapping. It identifies a class of modular functions whose inverses result directly from computing the inverse of the (coefficient) matrix used to specify a modular mapping. An efficient method of O(n/sup 2/) complexity is provided to formulate the problem of generating such modular mappings as an integer linear programming problem.

Modular time-space transformations have been recently proposed for algorithm mappings that cannot be described by affine functions. This paper extends affine data alignments to a new class of data alignments, called expanded modular data alignments (EMDAs), for algorithms that are mapped by modular time-space transformations. An EMDA is a set of modular data alignments (MDAs) which are described by affine functions module a constant vector. With an EMDA, multiple copies of a data array are mapped into target processors by different modular data alignments (MDAs) and therefore can be efficiently used with modular time-space transformations which may require several operations to access the same data at the same time. Conditions of EMDAs that guarantee local access of data entries are provided. These conditions cover initial data alignment, data movement during the computation, and the number of copies required to avoid unnecessary communications. These conditions can be used to derive the EMDA for a given modular mapping or to generate a modular mapping for a given EMDA so that communication due to data misalignment does not occur. Several examples are given to show that EMDAs are well suited for modular time-space mappings.

A multistage self-routing permutation network is presented. This network is constructed from concentrators and digit-controlled 2/spl times/4 switches. A destination-tag routing scheme is used to realize any arbitrary permutation. The network has O(log/sup 2/ N) gate-delay and uses O(N/sup 2/) VLSI-area, where N is the number of inputs. Assuming packet-switching is used for message transmission, the delay and VLSI-area of the network are smaller than those of any self-routing permutation network presented to date.>

Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.>

Affine space-time mappings have been extensively studied for systolic array design and parallelizing compilation. However, there are practical important cases that require other types of transformations. This paper considers so-called modular mappings described by linear transformations modulo a constant vector. Sufficient conditions for these mappings to be one-to-one are investigated for rectangular domains of arbitrary dimensions. It is shown that a sufficient condition for a modular mapping to be one-to-one is that its (n×n) coefficient matrix T has entries tii=±1 and tij=0 for i<j where < is a total order on {1,2,, n), n=domain dimension. These conditions are strengthened and extended for particular types of rectangular domains and affine transformations modulo a constant vector. The results of this paper can be used to identify a space of valid modular mappings of specific algorithms into time and space. They are illustrated by examples which include Cannon's matrix multiplication algorithm.

A method to migrate a task dynamically from a virtual SPMD machine to a virtual SIMD machine is proposed. It is assumed that the SIMD and SPMD virtual machine models only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language. The migration procedure does not require the SPMD PEs to be at the same location in the SPMD program at the time of the migration. This work is directly applicable to mixed-mode hybrid SIMDISPMD systems and part of the general problem of task migration in SIMDISPMD mixed-machine heterogeneous systems.

This paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes.>

If a processor develops a permanent fault during the execution of a task on a dynamically reconfigurable parallel machine, three recovery options are task migration to a fault-free subdivision, task migration to another submachine, and task redistribution. Quantitative models of these three reconfiguration schemes are analyzed, together with the cost of making the wrong choice, to develop guidelines for selecting among these methods in a practical dynamic reconfiguration implementation. A multistage cube or hypercube inter-processor network is assumed. The PASM and nCUBE 2 parallel machines are used as vehicles for studying the model parameters.

A method for the generation of detailed models of fault-tolerant processor arrays, based on stochastic Petri nets (SPNs), is presented. A compact SPN model of the array associates with each transition a set of attributes that includes a discrete probability distribution. Depending on the type of component and the reconfiguration scheme, these probabilities are determined using simulation or closed-form expressions and correspond to the survival of the array given that a number of components required by the reconfiguration process are faulty.>

The parameter method and data dependency method have been proposed as systematic design methodologies for systolic arrays. The authors describe the relationship between the two methodologies and show that the parameter method applies to a subclass of the algorithms that can be processed by the dependency method. The optimization procedure of the parameter method can be applied, in a restricted sense, within the framework of the dependency method. This procedure is used to derive an optimal array for the deconvolution algorithm.>

A 'state model' is proposed for solving the problem of routing and rerouting messages in the inverse augmented data manipulator (IADM) network. Necessary and sufficient conditions the reroutability of messages are established using this model, and destination tag schemes are derived. These schemes are simpler, more efficient, and require less complex hardware than previously proposed routing schemes. Two destination tag schemes are proposed. A universal rerouting algorithm is constructed based on one of the schemes. It finds a blockage-free path for any combination of multiple blockages if there exists such a path, and indicates the absence of such a path if there exists none. In addition, the state model is used to derive constructively a lower bound on the number of subgraphs which are isomorphic to the indirect binary n-cube network in the IADM network. This knowledge can be used to characterize properties of the IADM networks and for permutation routing in the IADM networks.>

Uniform dependence algorithms with arbitrary index sets are considered, and two computationally inexpensive methods to find their independent partitions are proposed. Each method has advantages over the other one for certain kinds of applications, and they both outperform previously proposed approaches in terms of computational complexity and/or optimality. Also, lower and upper bounds are given for the cardinality of maximal independent partitions. In multiple instruction multiple data (MIMD) systems, if different blocks of an independent partition are assigned to different processors, communications between processors will be minimized to zero. This is significant because the communications usually dominate the overhead in MIMD machines.>

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k>

The authors address the problem of identifying optimal linear schedules for uniform dependence algorithms so that their execution time is minimized. Procedures are proposed to solve this problem based on the mathematical solution of a nonlinear optimization problem. The complexity of these procedures is independent of the size of the algorithm. Actually, the complexity is exponential in the dimension of the index set of the algorithm, and for all practical purposes, very small due to the limited dimension of the index set of algorithms of practical interest. A particular class of algorithms for which the proposed solution is greatly simplified is considered, and the corresponding simpler organization procedure is provided.>

A general approach to hardware recognition is proposed for VLSI/WSI fault-tolerant processor arrays. The technique, called full use of suitable spares (FUSS), uses an indicator vector, the surplus vector, to guide the replacement of faulty processors within an array. Analytical study of the general FUSS algorithm shows that there is a linear relationship between the array size and the area of interconnect required for reconfiguration to be 100% successful. In an instance of FUSS, called simple FUSS, reconfiguration is done by shifting up to or down the surplus vector's entries. The surplus vector is progressively updated after each column is reconfigured. The reconfiguration is successful when the surplus vector becomes null. Simple FUSS is discussed in detail and evaluated. Simulations show that when the number of faulty processors is equal to that of space processors, simple FUSS can achieve a probability of survival as high as 99%.>

A state model is proposed for solving the problem of routing and rerouting messages in the inverse augmented data manipulator (IADM) network. Using this model, necessary and sufficient conditions for the reroutability of messages are established, and two then destination tag schemes are derived. For one of the schemes, rerouting is totally transparent to the sender of the message and any blocked line of a given type can be avoided. The spatiotemporal complexity is reduced from O(log N) (for previous techniques) to O(1). For the other scheme, rerouting is possible for any type of link blockage. A universal rerouting algorithm is constructed based on the second scheme, which finds a blockage-free path for any combination of multiple blockages if there exists such a path, and indicates absence of such a path if none exists. In addition, the state model is used to constructively derive a lower bound on the number of subgraphs which are isomorphic to the indirect binary n-cube network in the IADM network. This knowledge can be used to characterize properties of the IADM networks and for permutation routing in the IADM networks.>

A technique for partitioning and mapping algorithms into VLSI systolic arrays is presented in this paper. Algorithm partitioning is essential when the size of a computational problem is larger than the size of the VLSI array intended for that problem. Computational models are introduced for systolic arrays and iterative algorithms. First, we discuss the mapping of algorithms into arbitrarily large size VLSI arrays. This mapping is based on the idea of algorithm transformations. Then, we present an approach to algorithm partitioning which is also based on algorithm transformations. Our approach to the partitioning problem is to divide the algorithm index set into bands and to map these bands into the processor space. The partitioning and mapping technique developed throughout the paper is summarized as a six step procedure. A computer program implementing this procedure was developed and some results obtained with this program are presented.

A new approach to the design of gracefully degradable processor arrays is discussed. Fault tolerance and graceful degradation are achieved by simultaneously reconfiguring the processor array and the algorithm in execution. Two types of algorithm reconfigurability are considered, namely, row reconfigurability (RR) and row-column reconfigurability (RCR). correspondingly, two array reconfiguration schemes are discussed, i.e., successive row elimination (SRE) and alternate row-column elimination (ARCE). It is shown that the computations of any algorithm executable in a processor array can always be (re) organized so that the resultant algorithm has the RR and/or RCR properties. Upper bounds on the increase in execution time of an algorithm due to reorganization of computations for reconfigurability are derived. Detailed analysis of performance and reliability is done for both SRE and ARCE reconfiguration schemes. These reconfiguration techniques are applicable to any processor array and suitable for VLSI technology.

A major problem in executing algorithms in array processors is the implementation of broadcasts without unnecessary speed-up factor degradation. We discuss when and how broadcasts can be eliminated or reduced to easily implementable sequences of reduced local broadcasts. Algorithms are modelled as a structured set of indexed computations which operate on variables associated with a referencing or indexing function. The discussion is restricted to variables with linear indexing functions and to algorithms linearly scheduled for execution in array processors. Linear indexing functions are represented as affine matricial functions of the index set of the algorithm. The linear part of such representation is a coefficient matrix denoted the indexing matrix. Linear schedules are defined as linear time-space allocation functions mapping the computations of an algorithm into time and processors. We discuss necessary and sufficient conditions for the occurrence of broadcasts in a linearly scheduled algorithm. Necessary and sufficient conditions and constructive criteria are given for selecting linear schedules for which all broadcasts are eliminated or reduced to sequences of small local broadcasts.