Search

While data filter caches (DFCs) have been shown to be effective at reducing data access energy, they have not been adopted in processors due to the associated performance penalty caused by high DFC miss rates. In this article, we present a design that both decreases the DFC miss rate and completely eliminates the DFC performance penalty even for a level-one data cache (L1 DC) with a single cycle access time. First, we show that a DFC that lazily fills each word in a DFC line from an L1 DC only when the word is referenced is more energy-efficient than eagerly filling the entire DFC line. For a 512B DFC, we are able to eliminate loads of words into the DFC that are never referenced before being evicted, which occurred for about 75% of the words in 32B lines. Second, we demonstrate that a lazily word filled DFC line can effectively share and pack data words from multiple L1 DC lines to lower the DFC miss rate. For a 512B DFC, we completely avoid accessing the L1 DC for loads about 23% of the time and avoid a fully associative L1 DC access for loads 50% of the time, where the DFC only requires about 2.5% of the size of the L1 DC. Finally, we present a method that completely eliminates the DFC performance penalty by speculatively performing DFC tag checks early and only accessing DFC data when a hit is guaranteed. For a 512B DFC, we improve data access energy usage for the DTLB and L1 DC by 33% with no performance degradation.

Level-one data cache (L1 DC) and data translation lookaside buffer (DTLB) accesses impact energy usage as they frequently occur and each L1 DC and DTLB access uses significantly more energy than a register file access. Often, multiple memory operations will reference the same cache line using the same register, such as when iterating through an array. We propose to memoize L1 DC access information, such as the L1 DC data array way and the DTLB way, by associating this information with the register used to access it. When a load or store calculates the memory address, we detect whether the calculated address shares the cache line memoized with the base register. If so, we avoid the L1 DC tag array access and the DTLB access to determine the L1 DC way and instead use the memoized information. In addition, only a single data array way in a set-associative L1 DC needs to be accessed during a load instruction when the L1 DC way has been memoized. Our nonspeculative memoization approach can be applied before a speculative approach, allowing a significant reduction in data access energy usage for existing executables with no ISA modifications.

Superscalar processors take advantage of speculative execution to improve performance. When the speculation turns out to be incorrect, a recovery procedure is initiated. The back-end of the processor cannot be flushed due to having a mixture of both valid and invalid instructions. A basic solution is to wait for all valid instructions to retire and then purge the invalid instructions. However, if a long latency operation, such as a Last-level Cache (LLC) miss appears before the misspeculation point, the back-end recovery time significantly increases. Many proposed mechanisms selectively flush invalid instructions in order to speed up the back-end recovery. In general, these mechanisms rely on broadcasting some misprediction related tags to remove the instructions from any backend structures, such as ROB, LSQ, RS, etc. The hardware overhead in these mechanisms is nontrivial and can potentially affect the processor clock cycle time if they are on the critical path. Moreover, a checkpointing mechanism or a walker needs to be added to accelerate the recovery of the front-end register alias table (F-RAT). We propose a two-phase recovery mechanism which does not need any walking or broadcasting process and can still match the performance of the state-of-the-art recovery approaches. The first phase works similar to a typical basic recovery mechanism and the second phase is not triggered until the backend is stalled by an LLC miss load. In that case, the second phase treats the load as a misspeculation and recovers from this load. Since the LLC miss response time is usually much longer than the time to fill the entire pipeline with new instructions, in most cases our mechanism can completely overlap the branch misprediction recovery penalty with the cache miss penalty.

Store-queue-free architectures remove the store queue and use memory cloaking to communicate in-flight stores instead. In these architectures, frequent mispredictions may occur when the store to load dependencies are inconsistent. We present DMDP (Dynamic Memory Dependence Predication) which modifies the microarchitecture behavior for such loads to mitigate memory dependence mispredictions. When a given dependence is hard to predict, i.e., a given load occasionally depends on a particular store, but it is independent at other times, DMDP predicates the load so that the address of the load is compared with the address of the predicted store to compute a predicate. This predicate guides the load to obtain the value from either the cache or the colliding store. The predication provided by DMDP i) enables the loads and their dependent instructions to execute much earlier, ii) reduces the hardware complexity of store-queue-free mechanisms, and iii) reduces the number of mispredictions. DMDP outperforms a state-of-the-art store-queue-free architecture by 7.17% on Integer benchmarks and 4.48% on Float benchmarks in our Spec 2006 evaluation. We further show that despite executing extra predication instructions, DMDP is power efficient as it saves about 6.7% on EDP.

LaZy Superscalar is a processor architecture which delays the execution of fetched instructions until their results are needed by other instructions. This approach eliminates dead instructions and provides the necessary means to fuse dependent instructions across multiple control dependencies by explicitly tracking control and data dependencies through a matrix based scheduler. We present this novel redesign of scheduling, recovery and commit mechanisms and evaluate the performance of the proposed architecture. Our simulations using Spec 2006 benchmark suite indicate that LaZy Superscalar can achieve significant speed-ups while providing respectable power savings compared to a conventional superscalar processor.

Mower is a micro-architecture technique which targets the branch misprediction penalty in superscalar processors. It speeds-up the misprediction recovery process by dynamically evicting stale instructions and correcting the Register Alias Table (RAT) using explicit control dependency tracking. Tracking control dependencies is accomplished by using simple bit matrices. This low-overhead technique allows overlapping of the recovery process with instruction fetching, renaming and scheduling from the correct path. Our evaluation of the mechanism indicates that it yields performance very close to ideal recovery and provides up to 5% speed-up and 2% reduction in power consumption compared to a recovery mechanism using a reorder buffer and a walker. The simplicity of the mechanism should permit easy implementation of Mower in an actual processor.

We present a new static single assignment form which can be used by an optimizing compiler as its internal representation and the micro-architecture as its instruction set. This representation, Future Gated Single Assignment Form (FGSA), directly represents the use-def relationship of variables by employing the concept of congruence classes and the concept of future dependencies. We show that FGSA is efficiently computable by using a series of T1/T2 transformations, yielding an expected linear time algorithm for the construction of single assignment form. Our interval analysis method includes a novel transformation TR which eliminates irreducible loops without node splitting and combines computation of single-assignment form with irreducible loop elimination. The algorithm produces pruned single assignment form, rendering a separate pruning step unnecessary. In practice, the FGSA approach results in an average reduction of 7.7%, with a maximum of 67% in the number of gating functions compared to the pruned SSA form on the SPEC2000 benchmark suite, owing to its ability to represent dataflow within a congruence class by using a single gating function. We illustrate that FGSA is convenient to use as an internal representation in an optimizing compiler by presenting two case studies of optimization algorithms on FGSA.

The goal of computer architecture research is to design and build high performance systems that make effective use of resources such as space and power. The design process typically involves a detailed simulation of the proposed architecture followed by corrections and improvements based on the simulation results. Both simulator development and result analysis are very challenging tasks due to the inherent complexity of the underlying systems. The motivation of this work is to apply episode mining algorithms to a new domain, architecture simulation, and to prepare an environment to make predictions about the performance of programs in different architectures. We describe our tool called Episode Mining Tool (EMT), which includes three temporal sequence mining algorithms, a preprocessor, and a visual analyzer. We present empirical analysis of the episode rules that were mined from datasets obtained by running detailed micro-architectural simulations.

Bilgi çağı olarak tanımlanan günümüzde değişim çok hızlı yaşanmaktadır. Değişime ayak uydurabilen toplumlar ileriye daha rahat ilerlerken, bu değişimin gerisinde kalanlarsa başkalarına bağımlı yaşamaya devam etmektedirler. Dolayısıyla bilginin sürekli yeniden üretilmesi önemli bir problem olarak toplumların ve örgütlerin en önemli çabası durumundadır. Bu çabada ayrı ayrı kurumların veya örgütlerin başarılı olması hemen hemen imkansızdır. Hayatta kalmak isteyen kurumlar, aynı amacı paylaşan diğerleriyle ortak hareket etmek zorundadırlar. Bu bağlamda eğitimin öncüsü olan üniversitelerin de okullarla işbirliğine gitmesi, karşılıklı paylaşımda bulunmaları gerekmektedir.Bu araştırma, eğitim yöneticilerinin okul-üniversite işbirliğine ilişkin görüşlerini belirlemeyi amaçlamaktadır. Araştırmada yöneticilerin; okul-üniversite işbirliğinden ne anladıkları, okul-üniversite işbirliği ile yaptıkları, okul-üniversite işbirliği hakkındaki olumsuz düşünceleri ve üniversiteden neler bekledikleri tartışılmıştır.Araştırma verileri, Yalova'nın resmi okullarında görev yapan 5 okul müdürü ve il milli eğitim müdürüyle gerçekleştirilen mülakatlardan elde edilmiştir. Elde edilen veriler dört ana temaya ayrılarak betimsel analiz tekniklerine göre raporlaştırılmıştır.Araştırmanın sonucunda; eğitim yöneticilerimizin okul-üniversite işbirliğinin ne olduğunu anlayamadıkları ve dolayısıyla önemini kavrayamadıkları, okul-üniversite işbirliklerinden faydalanılabilmesi için eğitimde yerelleşmenin gerekli olduğu ve hizmet öncesi ve hizmet içi eğitimlerin okul-üniversite işbirliği bağlamında yeniden değerlendirilmesinin gerekli olduğu sonuçlarına ulaşılmıştır.Anahtar Kelimeler: okul-üniversite işbirliği, eğitimde yerelleşme, hizmet içi eğitim. Today which is called information age, the change is being lived so rapid. As the societies who could keep in step with the change are going up easily, the others that got behind this change, are still going on living in dependence on others. So the constant reproducing knowledge is the most important challenge of societies and organizations. It is almost impossible for a foundation or an organization to be successful on that target alone. Foundations that want to survive have to cooperate with others that have the same targets. In this context, the universities that are forerunner of education also have to make relationships, do mutual sharing with schools.By this research, it is aimed to find out the thoughts of educational administrators on school-university partnership. At the research, administrators?s thoughts on what they understand from school-university partnership, whatever they did in school-university partnership, their negative thoughts on school-university partnership and what they expect from university were discussed.The research datas, were collected from 5 school administrators who are performing at official schools of Yalova and administrator of city?s national education via interviews. The datas collected were organised into four main theme according to the techniques of descriptive analysis.As a result of the research, these are found out: our educational administrators don?t know what school-university relationship is and so can?t understand its importance; to reap benefits of school-university partnership, the localization of education is a necessity; and the ways of inservice education must be reevaluated in the context of school-university partnership.Key words: school-university partnership, localization in education, inservice education. 107

We introduce the concept of future values. Using future values it is possible to represent programs in a new control-flow form such that on any control flow path the data-flow aspect of the computation is either traditional (i.e., definition of a value precedes its consumers), or reversed (i.e., consumers of a value precede its definition). The representation hence allows unrestricted code motion since ordering of instructions are not prohibited by the data dependencies. We present a new program representation called Recursive Future Predicated Form (RFPF) which implements the concept. RFPF subsumes general if-conversion and permits unrestricted code motion to the extent that the whole procedure can be reduced to a single block. We develop algorithms which enable instruction movement in acyclic as well as cyclic regions and give examples of various optimizations in RFPF form.

We show that a multi-threaded processor that is aware of the processor state in a fine-grain manner can improve single-thread performance significantly by assigning the task of maintaining the correct processor state to an independent thread. We develop fine-grain state maintenance techniques that can be applied in multi-threaded environments and present a fine-grain state application of runahead execution where the data values dependent on a missed load are treated as damaged values. These values are verified and recovered as necessary by an independent thread. We evaluate an SMT-like fine grain state processor and show that it obtains an average of 38.9% and up to 160.0% better performance than coarse-grain baseline processors on the SPEC CFP2000 benchmark suite.

Publisher Summary This chapter focuses on the architecture description language (ADL)++, which allows automatic synthesis of cycle-accurate simulators, assemblers, and disassemblers from a specification written in the language. Its compiler is also implemented as part of the flexible architecture simulation toolset (FAST). The ADL++ language supports an execution model that is suitable for expressing a broad class of processor architectures. This execution model supports specification of the microarchitecture including pipelines, control, and the memory hierarchy including instruction and data caches, the assembly language syntax, and the binary representation. Instead of modeling hardware components, ADL++ explicitly models the instruction flow through some placeholders called pipeline stages, which make up the microarchitecture. This flow is tightly coupled with a clock built into the language, and the programmer explicitly specifies when an instruction can move from one stage to the next. The challenges posed by complex instruction set architectures are described by presenting the unique properties of Intel's IA-32 instruction set architecture, which includes variable length instructions, too many addressing modes and overlapping registers, as well as mixed arguments in the instruction set. ADL++ artifacts can be used to describe the behavior of synchronous pieces of hardware and can be used to create arrays of artifacts, which then can be used as the building blocks of a more complicated hardware structure.

Profiling can effectively analyze program behavior and provide critical information for feedback-directed or dynamic optimizations. Based on memory profiling, reuse distance analysis has shown much promise in predicting data locality for a program using inputs other than the profiled ones. Both whole-program and instruction-based locality can be accurately predicted by reuse distance analysis. Reuse distance analysis abstracts a cluster of memory references for a particular instruction having similar reuse distance values into a locality pattern. Prior work has shown that a significant number of memory instructions have multiple locality patterns, a property not desirable for many instruction-based memory optimizations. This paper investigates the relationship between locality patterns and execution paths by analyzing reuse distance distribution along each dynamic path to an instruction. Here a path is defined as the program execution trace from the previous access of a memory location to the current access. By differentiating locality patterns with the context of execution paths, the proposed analysis can expose optimization opportunities tailored only to a specific subset of paths leading to an instruction. In this paper, we present an effective method for path-based reuse distance profiling and analysis. We have observed that a significant percentage of the multiple locality patterns for an instruction can be uniquely related to a particular execution path in the program. In addition, we have also investigated the influence of inputs on reuse distance distribution for each path/instruction pair. The experimental results show that the path-based reuse distance is highly predictable, as a function of the data size, for a set of SPEC CPU2000 programs.

Designing, testing, and producing a new computer processor is a complex and very expensive process. To reduce costly mistakes in hardware, the microarchitecture is usually designed and tested with the aid of a software simulator. The FAST System enables microarchitects to develop architecture simulators rapidly and is less error-prone than using a high level language such as C. In this paper, we describe how the FAST System's Architecture Description Language (ADL) has been extended to facilitate the description of complex instruction sets such as Intel's IA-32 instruction set architecture. In this respect, we demonstrate that the notion of inheritence, a key concept in object oriented programming languages can be extended for selective inheritence to enable the specification of complex instruction set architectures in architecture description languages.

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.

Modern microprocessor designs continue to obtain impressive performance gains through increasing clock rates and advances in the parallelism obtained via micro-architecture design. Unfortunately, corresponding improvements in memory design technology have not been realized, resulting in latencies of over 100 cycles between processors and main memory. This ever-increasing gap in speed has pushed the current memory-hierarchy approach to its limit.Traditional approaches to memory-hierarchy management have not yielded satisfactory results. Hardware solutions require more power and energy than desired and do not scale well. Compiler solutions tend to miss too many optimization opportunities because of limited compile-time knowledge of run-time behavior. This paper explores a different approach that combines both approaches by making use of the static knowledge obtained by the compiler in the dynamic decision making of the micro-architecture. We propose a memory-hierarchy design based on working sets that uses compile-time annotations regarding the working set of memory operations to guide cache placement decisionsOur experiments show that a working-set-based memory hierarchy can significantly reduce the miss rate for memory-intensive tiled kernels by limiting cross interference. The working-set-based memory hierarchy allows the compiler to tile many loops without concern for cross interference in the cache, making tile size choice easier. In addition, the compiler can more easily tailor tile choices to the separate needs of different working sets.

This project considered various sources of power consumption in general purpose high-performance and embedded processors and developed techniques for lowering the power consumption without significant sacrifice in performance. We have designed low power data caches and low power external data buses that can he used for both superscalar and embedded processors. For superscalar processors we have designed low complexity memory disambiguation mechanism, power efficient instruction issue mechanism, and load/store reuse techniques. For embedded processors we have developed techniques that allow us to achieve performance while operating on compacted code and data. The various techniques that were developed have been implemented as part of gcc compiler and the FAST simulation system. Experimentation was carried to demonstrate the utility of the techniques.

We describe the UPFAST system that automatically generates a cycle level simulator, an assembler and a disassembler from a microarchitecture specification written in a domain specific language called the Architecture Description Language (ADL). Using the UPFAST system, it is easy to retarget a simulator for an existing architecture to a modified architecture since one has to simply modify the input specification and the new simulator is generated automatically. UPFAST also allows porting of simulators to different platforms with minimal effort. We have been able to develop three simulators ranging from simple pipelined processors to complicated out-of-order issue processors over a short period of three months. While the specifications of the architectures varied from 5000 to 6000 lines of ADL code, the sizes of automatically generated software varied from 20000 to 300000 lines of C++ code. The automatically generated simulators are less than 2 times slower than hand coded simulators for similar architectures.

We empirically demonstrate that in order to take advantage of increasing issue widths, superscalar processors require quadratically growing instruction window sizes. Since conventional central window design aims to provide full data fan-out to all the instructions which are in the window, designing large instruction windows using conventional techniques is not feasible. We show that full data fan-out is not necessary for achieving high performance when a novel approach is used to distribute the values. We use direct matching using a small on chip memory called the wait memory to implement the instruction window and bring in a small subset of instructions which are likely to become ready into a match unit where instruction selection and operand matching tasks are performed. We show that the match unit needs to grow only linearly with the issue width. We use SPEC95 benchmarks to demonstrate that at a given instruction window size our algorithm provides over 90 percent of the IPC that can be obtained by a central window implementation that provides full data fan-out.

We present a novel approach which combines compiler, instruction set, and microarchitecture support to turn off functional units that are idle for long periods of time for reducing static power dissipation by idle functional units using power gating [2,9]. The compiler identifies program regions in which functional units are expected to be idle and communicates this information to the hardware by issuing directives for turning units off at entry points of idle regions and directives for turning them back on at exits from such regions. The microarchitecture is designed to treat the compiler directives as hints ignoring a pair of off and on directives if they are too close together. The results of experiments show that some of the functional units can be kept off for over 90% of the time at the cost of minimal performance degradation of under 1%.

Modern processors and compilers hide long memory latencies through non-blocking loads or explicit software prefetching instructions. Unfortunately, each mechanism has potential drawbacks. Non-blocking loads can significantly increase register pressure by extending the lifetimes of loads. Software prefetching increases the number of memory instructions in the loop body. For a loop whose execution time is bound by the number of loads/stores that can be issued per cycle, software prefetching exacerbates this problem and increases the number of idle computational cycles in loops.