Members of the Western Michigan Transformative Interdisciplinary Human+AI Research Group have been engaged in two consecutive NSF-funded projects to promote AI readiness in diverse STEM disciplines. Putting equal emphasis on theory and practice, our goal is to instill knowledge and competency in safe, secure, and reliable AI across a wide range of learners from high school students through to university students and practitioners who wish to upskill. The second project that is currently underway has a specific focus on machine-assisted processing of massive data. This presentation focuses on the development of immersive learning experiences.

Data integrity is critical to the secure operation of a computer system. Applications need to know that the data that they access is trustworthy. Many current production-level integrity models are tightly coupled to a specific domain, (e.g., databases), or only apply after the fact (e.g., backups). In this paper we propose a recommendation-based trust model, called Admonita, for data integrity that is applicable to any structured data in a system and provides a measure of trust to applications on-the-fly. The proposed model is based on the Biba integrity model and utilizes the concept of an Integrity Verification Procedure (IVP) proposed by Clark-Wilson. Admonita incorporates subjective logic to maintain the trustworthiness of data and applications in a system. To prevent critical applications from losing trust, Admonita also incorporates the principle of weak tranquility to ensure that highly trusted applications can maintain their trust levels. We develop a simple algebra around these elements and describe how it can be used to calculate the trustworthiness of system entities. By applying subjective logic, we build a powerful, artificial and reasoning trust model for implementing data integrity.

Integer errors continue to create vulnerabilities. In fact, Integer Overflow or Wraparound is listed at position 11 in the 2020 CWE Top 25 Most Dangerous Software Weaknesses. This poster describes the Expression Evaluation (EE) visualization tool that helps students understand the type conversions that take place implicitly within a C program. This tool depicts step-wise the coercions that take place within the evaluation of a user specified expression with mixed integer type operands. The system enables students to create unlimited examples to test their understanding. The tool was evaluated in the classroom and shown to be easy to use and effective.

In many undergraduate programs, students primarily write code in Java or other scripting languages. Yet C and C++ are widely used when performance is important. Poor understanding of a C program's layout in memory and its execution leads to the introduction of security vulnerabilities. We present the SecureCvisual system, which is designed to help students learn to develop more secure and robust C programs.

Seemingly small coding errors can create significant vulnerabilities in C programs. This often occurs due to memory being overwritten in unexpected ways. If a student understands where program variables appear in the process address space, then she can understand the effect of writing beyond the memory allocated to a variable. With this understanding, she can tie her code to its effect within an executing process and is more likely to appreciate the significance of these seemingly harmless errors and to avoid them. We have developed a program analysis and visualization tool to help students understand the impact of common memory errors with the goal to help students avoid introducing these errors into their code. The visualization is through the Program Address Space (PAS) window within a larger system for analysis and visualization of security issues in C programs. The larger system is called SecureCvisual. In this paper, we describe our experience with teaching students fundamental concepts about process address spaces and the impact of buffer overflows using the PAS window. We also present the results from an evaluation of the tool. Our results indicate that students found the tool useful and that it enhanced the course in which it was used.

The integrity of systems files is necessary for the secure functioning of an operating system. Integrity is not generally discussed in terms of complete computer systems. Instead, integrity issues tend to be either tightly coupled to a particular domain (e.g. database constraints), or else so broad as to be useless except after the fact (e.g. backups). Often, file integrity is determined by who modifies the file or by a checksum. This paper focuses on a general model of the internal integrity of a file. Even if a file is modified by a subject with trust or has a valid checksum, it may not meet the specification of a valid file. An example would be a password file with no user assigned a user id of 0. In this paper, we describe a language called Maia that provides a means to specify what the contents of a valid file should be. Maia can be used to specify the format and valid properties of system configuration files, PNG files and others. We give a structural operational semantics of Ma ia and discuss an initial implementation within a mandatory integrity system.

Integer errors can introduce significant vulnerabilities into C programs. We have developed a program analysis and visualization tool to help students understand integer representation and type conversions with the goal to help students avoid introducing these errors into the code they develop. The visualization is through the Integer Representation (IR) window within a larger system for analysis and visualization of security issues in C programs. The system is called the Visualization and Analysis for C Code Security (VACCS) system. In this paper, we describe our experience with teaching fundamental aspects of integer security in a junior-level systems programming course, the IR window, and an evaluation of the tool. Our results indicate that students found the tool to be useful and that it enhanced the course in which it was used.

On modern computer systems, the performance of an application depends largely on its locality. Current compiler static locality analysis has limited applicability due to limited run-time information. By instrumenting and running programs, training-based locality analysis is able to predict the locality of an application based on the size of the input data accurately; however, it is costly in terms of time and space. In this paper, we combine source-code analysis with training-based locality analysis to construct a supervised-learning model parameterized only by the source code properties. This model is the first to be able to predict the upper bound of data reuse change (locality pattern complexity) at compile time for loop nests in array-based programs without the need to instrument and run the program. The result is the ability to predict how virtual memory usage grows as a function of the input size efficiently. We have evaluated our model using array-based code as input to a variety of classification algorithms. These algorithms include Naive Bayes, Decision tree, and Support Vector Machine (SVM). Our experiments show that SVM outperforms the other classifiers with 97% precision, a 97% true positive rate and a 1% false positive rate. We are able to predict the growth rate of memory usage in unseen scientific code accurately without the need to instrument and run the program. This work represents a significant step in developing an accurate static memory usage predictor for use in Virtual Machines (VMs) in cloud data centers.

Protection of data in cloud computing is a critical problem for many enterprises. We propose a solution that protects sensitive data outsourced to a cloud throughout their entire life cycle—both in the cloud as well as outside of the cloud (e.g., during transmission to or from the cloud). Our solution, known as Active Data Bundles using Secure Multi-Party Computation (ADB-SMC), uses: (i) active data bundles (ADBs)—for self-protecting data; (ii) ciphertext-policy attribute-based encryption—for fine-grained access control; and, (iii) threshold RSA—for secure key management. We describe components and design of ADB-SMC and present the pseudocode for creating ADB to outsource data to the cloud. We implemented a prototype of the solution and compared its overhead with the overhead of the approach known as Active Bundles with Trusted Third Party (ABTTP). The results of performance tests show that the execution time overhead for ADBSMC is acceptable.

This paper describes a pedagogical system to visualize program execution.1 The visualization is designed to help students understand how to develop more secure and robust C programs. The system provides several perspectives on the execution including: the values of registers and the logical address space, a call graph, the file descriptor and inode tables, and the handling of sensitive data like passwords and keys. These visualizations are designed to help students understand fundamental concepts such as: buffer overflows, integer overflows, proper handling of sensitive data and application of the principle of least privilege in several contexts including file operations, secure SUID programming, and use and management of the process environment.

UNIXvisual is a user-level visualization tool designed to facilitate the study and teaching of access control in UNIX. UNIXvisual is aimed at both novice users, who need only to control access to their own files, and students of computer security, who need a deeper and more comprehensive understanding. The system allows students to analyze permission settings in the underlying real file system, as well as in a combination of real and pseudo file systems defined through a specification file. It also allows a student to trace the value and effect of credentials within an executing process. UNIXvisual gives instructors flexibility in the allocation of lecture time by supporting self-study, lowers the overhead required for teaching access control by running under an ordinary user account, and enhances learning through the use of visualization. We also present the results of an evaluation of UNIXvisual within a junior-level course on concurrent computing. The evaluation indicated that UNIXvisual helped students understand UNIX permissions and enhanced the course coverage of UNIX permissions, regardless of their prior UNIX experience.

This paper describes UNIXvisual, which helps students learn access control in UNIX. UNIXvisual is aimed both at novice users, who need only to control access to their own files, and students of computer security, who need a deeper and more comprehensive understanding. UNIXvisual allows students to analyze permission settings without the need for a special environment. It allows a student to trace the value and effect of credentials within an executing process. It also provides a mechanism for instructors to give quizzes UNIXvisual gives instructors flexibility in covering the material by supporting self-study, lowers the overhead required for teaching access control by running under an ordinary user account, and enhances learning by leveraging visualization. UNIXvisual is available for download and runs on the Linux and MacOS platforms.

This paper presents RBACvisual, a user-level visualization tool designed to facilitate the study and teaching of the role-based access control (RBAC) model, which has been widely used in companies to restrict access to authorized users. RBACvisual provides two graphical abstractions of the underlying specification. Policies can be input and modified graphically or using text-based files. Students can use an embedded Query system to answer commonly asked questions and to test their understanding of a given policy. A Practice subsystem is also provided for instructors to assign quizzes to students; the answers can be sent to the instructor via email. We also present the results of an evaluation of RBACvisual within a senior-level course on information security. The student feedback was positive and indicated that RBACvisual helped students understand the model and enhanced the course.

Cryptography and access control are perhaps the two most fundamental mechanisms for data protection. This workshop presents hands-on methods for teaching cryptography and access control that leverage software tools developed with funding from the NSF. The workshop will proceed in two sessions. The first session will address teaching well-known ciphers (including Vigenère, DES, AES, RSA, and SHA) and elliptic-curve cryptography using tools from the cryptoVisual software suite. These tools step students through an algorithm with either the system or the student computing the result of each step. The second session will address access control and the Multilevel Security, Role Based Access Control, and Domain Type Enforcement models using tools from the acVisual software suite. These tools support graphical policy development and analysis. The presenters have used this material in undergraduate courses in Cryptography and Computer Security. The tools have been used and evaluated favorably at multiple institutions. Participants will install and use the software on their own laptops running Linux, Windows, or MacOS. The acVisual software runs natively on Linux and MacOS and through a Linux virtual machine under Windows. The cryptoVisual software suite is available at http://www.cs.mtu.edu/~shene/NSF-4/. The acVisual software suite is available at http://acv.cs.mtu.edu.

Information security continues to be a pressing issue for industry and government. Perhaps the two most fundamental mechanisms for controlling access to information are cryptography and access control systems. This paper presents MLSvisual, a tool that helps students learn the multi-level(Bell-LaPadula) access control model. MLSvisual allows students to create, explore, and modify an MLS policy through a graphical visualization system. A query system can be used by students to test their understanding of a given policy. Instructors can utilize a test function in the tool to assign an exercise or quiz, with answers sent to them via email. We also present the results of an evaluation of MLSvisual within a senior-level course on information security. This evaluation received positive feedback and showed that MLSviusal helped the understanding of the Bell-LaPadula model and enhanced the course. We believe that this user-level tool will help instructors to teach this material more effectively, and make teaching this material more practical in resource-constrained environments.

Feedback-directed optimization has developed into an increasingly important tool in designing optimizing compilers. Based upon profiling, memory distance analysis has shown much promise in predicting data locality and memory dependences, and has seen use in locality based optimizations and memory disambiguation. In this paper, we apply a form of memory distance, called store distance, to the problem of memory disambiguation in out-of-order issue processors. Store distance is defined as the number of store references between a load and the previous store accessing the same memory location. By generating a representative store distance for each load instruction, we can apply a compiler/micro-architecture cooperative scheme to direct run-time load speculation. Using store distance, the processor can, in most cases, accurately determine on which specific store instruction a load depends according to its store distance annotation. Our experiments show that the proposed store distance method performs much better than the previous distance based memory disambiguation scheme, and yields a performance very close to perfect memory disambiguation. The store distance based scheme also outperforms the store set technique with a relatively small predictor space and achieves performance comparable to that of a 16K-entry store set implementation for both floating point and integer programs.

Current trends in modern out-of-order processors involve implementing deeper pipelines and a large instruction window to achieve high performance. However, as pipeline depth increases, the branch misprediction penalty becomes a critical factor in overall processor performance. Current approaches to handling branch mispredictions either incrementally roll back to in-order state by waiting until the mispredicted branch reaches the head of the reorder buffer, or utilize checkpointing at branches for faster recovery. Rolling back to in-order state stalls the pipeline for a significant number of cycles and checkpointing is costly.This paper proposes a fast recovery mechanism, called Eager Misprediction Recovery (EMR), to reduce the branch misprediction penalty. Upon a misprediction, the processor immediately starts fetching and renaming instructions from the correct path without restoring the map table. Those instructions that access incorrect speculative values wait until the correct data are restored; however, instructions that access correct values continue executing while recovery occurs. Thus, the recovery mechanism hides the latency of long branch recovery with useful instructions.EMR achieves a mean performance improvement very close to a recovery mechanism that supports checkpointing at each branch. In addition, EMR provides an average of 9.0% and up to 19.9% better performance than traditional sequential misprediction recovery on the SPEC2000 benchmark suite.

With the ever-increasing pervasiveness of the Internet and its stringent performance requirements, network system designers have begun utilizing specialized chips to increase the performance of network functions. To increase performance, many more advanced functions, such as traffic shaping and policing, are being implemented at the network interface layer to reduce delays that occur when these functions are handled by a general-purpose CPU. While some designs use ASICs to handle network functions, many system designers have moved toward using programmable network processors due to their increased exibility and lower design cost. In this paper, we describe a code generation technique designed for the Agere Payload Plus network processor. This processor utilizes a multi-block pipeline containing a Fast Pattern Processor (FPP) for classification, a Routing Switch Processor (RSP) for traffic management and a third block, the Agere Systems Interface (ASI), which provides additional functionality for performance. This paper focuses on code generation for the clustered VLIW compute engines on the RSP. Currently, due to the real-time nature of the applications run on the APP, the programmer must lay out and partition the application-specific data by hand to get good performance.The major contribution of this paper is to remove the need for hand partitioning for the RSP compute engines. We propose both a greedy code-generation approach that achieves harmonic mean performance equal to code that has been hand partitioned by an application programmer and a genetic algorithm that achieves a harmonic mean speedup of 1.08 over the same hand-partitioned code. Achieving harmonic mean performance that is equal to or better than hand partitioning removes the need to hand code for performance. This allows the programmer to spend more time on algorithm development.

Scalar replacement is an effective optimization for removing memory accesses. However, exposing all possible array reuse with scalars may cause a significant increase in register pressure, resulting in register spilling and performance degradation. We present a low cost method to predict the register pressure of a loop before applying scalar replacement on high-level source code, called pseudo-schedule register prediction (PRP), that takes into account the effects of both software pipelining and register allocation. PRP attempts to eliminate the possibility of degradation from scalar replacement due to register spilling while providing opportunities for a good speedup. PRP uses three approximation algorithms: one for constructing a data dependence graph, one for computing the recurrence constraints of a software pipelined loop, and one for building a pseudo-schedule. Our experiments show that PRP predicts the floating-point register pressure within 2 registers and the integer register pressure within 2.7 registers on average with a time complexity of O(n/sup 2/) in practice. PRP achieves similar performance to the best previous approach, having O(n/sup 3/) complexity, with less than one-fourth of the compilation time on our test suite.

ThreadMentor is a multiplatform pedagogical tool designed to ease the difficulty in teaching and learning multithreaded programming. It consists of a C++ class library and a visualization system. The class library supports many thread management functions and synchronization primitives in an object-oriented way, and the visualization system is activated automatically by a user program and shows the inner working of every thread and every synchronization primitive on-the-fly. Events can also be saved for playback. In this way, students will be able to visualize the dynamic behavior of a threaded program and the interaction among threads and synchronization primitives.

Abstract This paper describes our experiments comparing multiple scalar replacement algorithms to evaluate their effectiveness on entire scientific application benchmarks within the context of a production‐level compiler. We investigate at what point aggressive scalar replacement becomes detrimental and which dependence tests are necessary to give scalar replacement enough information to be effective. As many commercial optimizing compilers may include some version of scalar replacement as an optimization, it is important to determine how aggressive these algorithms need to be. Previously, no study has examined ‘how much’ scalar replacement is sufficient and effective within the context of an existing highly optimizing compiler. Our experiments show that, on whole programs, simple algorithms and simple dependence analysis capture nearly all opportunities for scalar replacement found in scientific application benchmarks. While additional aggressiveness may lead to some performance gain in some individual loops, it also leads to performance degradation too often to be worth the risk when considering entire applications. Algorithms restricted to value reuse over at most one loop iteration and to fully redundant array references give the best results. Our experiment further shows that scalar replacement is not only an effective optimization, but also a feasible one for commercial optimizers since the simple algorithms are not computationally expensive. Based upon our findings, we conclude that scalar replacement ought to be a part of any highly optimizing compiler because of its low cost and significant potential gain. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents our effort in designing pedagogical tools for teaching message passing using channels. These tools include a class library that supports channels, a visualization system that helps students see the execution behavior of threads and message passing, and a topology editor that provides an environment for students to design network topologies. Moreover, since we have made sure the uniformity of the channel de.nition across the thread, parallel and distributed environments, porting a threaded program to a parallel/distributed environment is easy.

A number of communication libraries have been written to support concurrent programming. For a variety of reasons, these libraries generally are not well-suited for use in undergraduate courses. We have written a communication library uniquely tailored to an academic environment. The library provides two levels of communication abstraction (topology and channel) and supports communication among threads, processes on the same machine, and processes on different machines, via a unified interface. The routines facilitate controlled message loss along channels and can be integrated with an existing graphical tool that supports visualization of the communication that occurs. An editor has been developed for automatic code generation for arbitrary topologies via a graphical interface. All these tools run over Solaris, Linux, and Windows.

Many techniques for increasing the amount of instruction-level parallelism (ILP) put increased pressure on the registers inside a CPU. These techniques allow for more operations to occur simultaneously at the cost of requiring more registers to hold the operands and results of those operations, and importantly, more ports on the register banks to allow for concurrent access to the data. One approach of ameliorating the number of ports on a register bank (the cost of ports in gates varies as N/sup 2/ where N is the number of ports, and adding ports increases access time) is to have multiple register banks with fewer ports, each attached to a subset of the available functional units. This reduces the number of ports needed on a per-bank basis, but can slow operations if a necessary value is not in an attached register bank as copy operations must be inserted. Therefore, there is a circular dependence between assigning operations to functional units and assigning values to register banks. We describe an approach that produces good code by separating partitioning from scheduling and register assignment. Our method is independent of both the scheduling technique and register assignment method used.

All modern operating systems support multithreaded programming (MTP). To ensure our students can lead the trend of computer science in the foreseeable future, we have been teaching MTP for four years [6]. Our experience shows that the paradigm shift from sequential to multithreaded causes students significant problems [7], such as (1) MTP requires a new mindset, (2) multithreaded program behavior is dynamic, making debugging very difficult, (3) proper synchronization is more difficult tha anticipated, and (4) programming interfaces are usually more complex than necessary, causing students to spend time in learning the system details rather than the fundamentals.

Article Free Access Share on A visualization system for multithreaded programming Authors: Michael Bedy Department of Computer Science, Michigan Technological University, Houghton, MI Department of Computer Science, Michigan Technological University, Houghton, MIView Profile , Steve Carr Department of Computer Science, Michigan Technological University, Houghton, MI Department of Computer Science, Michigan Technological University, Houghton, MIView Profile , Xianlong Huang Department of Computer Science, Michigan Technological University, Houghton, MI Department of Computer Science, Michigan Technological University, Houghton, MIView Profile , Ching-Kuang Shene Department of Computer Science, Michigan Technological University, Houghton, MI Department of Computer Science, Michigan Technological University, Houghton, MISearch about this author Authors Info & Claims SIGCSE '00: Proceedings of the thirty-first SIGCSE technical symposium on Computer science educationMay 2000Pages 1–5https://doi.org/10.1145/330908.331798Published:01 March 2000Publication History 24citation607DownloadsMetricsTotal Citations24Total Downloads607Last 12 Months46Last 6 weeks4 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 SiteeReaderPDF

Modern architectural trends in instruction-level parallelism (ILP) are to increase the computational power of microprocessors significantly. As a result the demands on memory have increased. Unfortunately, memory systems have not kept pace. Even hierarchical cache structures are ineffective if programs do not exhibit cache locality. Because of this compilers need to be concerned not only with finding ILP to utilize machine resources effectively, but also with ensuring that the resulting code has a high degree of cache locality. One compiler transformation that is essential for a compiler to meet the above objectives is unroll-and-jam, or outer-loop unrolling. Previous work either has used a dependence-based model to compute unroll amounts, significantly increasing the size of the dependence graph, or has applied a more brute force technique. In this paper, we present an algorithm that uses a linear-algebra-based technique to compute unroll amounts. This technique results in an 84% reduction over dependence-based techniques in the total number of dependences needed in our benchmark suite. Additionally, there is no loss in optimization performance over previous techniques and a more elegant solution is utilized.

The goal of the LAPACK project is to provide efficient and portable software for dense numerical linear algebra computations. By recasting many of the fundamental dense matrix computations in terms of calls to an efficient implementation of the BLAS (Basic Linear Algebra Subprograms), the LAPACK project has, in large part, achieved its goal. Unfortunately, the efficient implementation of the BLAS results often in machine-specific code that is not portable across multiple architectures without a significant loss in performance or a significant effort to reoptimize them. This article examines wheter most of the hand optimizations performed on matrix factorization codes are unnecessary because they can (and should) be performed by the compiler. We believe that it is better for the programmer to express algorithms in a machine-independent form and allow the compiler to handle the machine-dependent details. This gives the algorithms portability across architectures and removes the error-prone, expensive and tedious process of hand optimization. Although there currently exist no production compilers that can perform all the loop transformations discussed in this article, a description of current research in compiler technology is provided that will prove beneficial to the numerical linear algebra community. We show that the Cholesky and optimized automaticlaly by a compiler to be as efficient as the same hand-optimized version found in LAPACK. We also show that the QR factorization may be optimized by the compiler to perform comparably with the hand-optimized LAPACK version on modest matrix sizes. Our approach allows us to conclude that with the advent of the compiler optimizations dicussed in this article, matrix factorizations may be efficiently implemented in a BLAS-less form

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality . In the this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. To validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. Experiments illustrate that for kernels our model and algorithm can select and achieve the best loop structure for a nest. For over 30 complete applications, we executed the original and transformed versions and simulated cache hit rates. We collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. To our knowledge, these studies are the first of such breadth and depth. We found performance improvements were difficult to achieve bacause benchmark programs typically have high hit rates even for small data caches; however, our optimizations significanty improved several programs.

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. In this paper, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. We demonstrate that these program transformations are useful for optimizing many programs.

Abstract Most conventional compilers fail to allocate array elements to registers because standard data‐flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating‐point registers, which are most often used as temporary repositories for subscripted variables. This paper presents a source‐to‐source transformation, called scalar replacement, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The scalar replaced variables are more likely to be assigned to registers by the coloring‐based register allocators found in most compilers than are their unreplaced counterparts. The algorithm presented here extends previous techniques for scalar replacement by allowing the presence of forward conditional control flow within loop bodies through the mapping of partial redundancy elimination to scalar replacement. Finally, experimental results show that scalar replacement is extremely effective. On kernels, integer‐factor improvements over code generated by a good optimizing compiler of conventional design are possible.

Over the past decade, microprocessor design strategies have focused on increasing the computational power on a single chip. Because computations often require more data from cache per floating-point operation than a machine can deliver and because operations are pipelined, idle computational cycles are common when scientific applications are executed. To overcome these bottlenecks, programmers have learned to use a coding style that ensures a better balance between memory references and floating-point operations. In our view, this is a step in the wrong direction because it makes programs more machine-specific. A programmer should not be required to write a new program version for each new machine; instead, the task of specializing a program to a target machine should be left to the compiler. But is our view practical? Can a sophisticated optimizing compiler obviate the need for the myriad of programming tricks that have found their way into practice to improve the performance of the memory hierarchy? In this paper we attempt to answer that question. To do so, we develop and evaluate techniques that automatically restructure program loops to achieve high performance on specific target architectures. These methods attempt to balance computation and memory accesses and seek to eliminate or reduce pipeline interlock. To do this, they estimate statically the balance between memory operations and floating-point operations for each loop in a particular program and use these estimates to determine whether to apply various loop transformations. Experiments with our automatic techniques show that integer-factor speedups are possible on kernels. Additionally, the estimate of the balance between memory operations and computation, and the application of the estimate are very accurate—experiments reveal little difference between the balance achieved by our automatic system that is made possible by hand optimization.

An attempt was made to determine whether a compiler can automatically restructure computations well enough to avoid the need for hand blocking. To that end, programs in LAPACK were studied for which it was possible to examine both the block version and the corresponding point algorithm. For each of these programs, it was determined whether a plausible compiler technology could succeed in obtaining the block version from the point algorithm. The results are encouraging: one can block triangular and trapezoidal loops, and many of the problems introduced by complex dependence patterns can be overcome by the use of the transformation known as index-set splitting. In addition, it was shown that knowledge about which operations commute can enable a compiler to succeed in blocking codes that could not be blocked by any compiler based strictly on dependence analysis.>

Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.