Transactions Chasing Scalability and Instruction Locality on Multicores

For several decades, online transaction processing (OLTP) has been one of the main server applications that drives innovations in the data management ecosystem, and in turn the database and computer architecture communities. Recent hardware trends oblige software to overcome two major challenges against systems scalability on modern multicore processors: (1) exploiting the abundant thread-level parallelism across cores and (2) taking advantage of the implicit parallelism within a core. The traditional design of the OLTP systems, however, faces inherent scalability problems due to its tightly coupled components. In addition, OLTP cannot exploit the full capability of the micro-architectural resources of modern processors because of the conventional scheduling decisions that ignore the cache locality for transactions. As a result, today’s commonly used server hardware remains largely underutilized leading to a huge waste of hardware resources and energy. .... In this thesis, we first identify the unbounded critical sections of traditional OLTP systems as the main enemy of thread-level parallelism. We design an alternative shared-everything system based on physiological partitioning (PLP) to eliminate the unbounded critical sections while providing an infrastructure for low-cost dynamic repartitioning and without introducing high-cost distributed transactions. Then, we demonstrate that L1 instruction cache stalls are the dominant factor leading to underutilization in the commodity servers. However, we also observe that independently of their high-level functionality, transactions running in parallel on a multicore system share significant amount of common instructions. By adaptively spreading the execution of a transaction over multiple cores through thread migration or multiplexing transactions on one core, we enable both an ample L1 instruction cache capacity for a transaction and reuse of common instructions across concurrent transactions. .... As the hardware demands more from the software to exploit the complexity and parallelism it offers in the multicore era, this work would change the way we traditionally schedule transactions. Instead of viewing a transaction as a single big task, we split it into smaller parts that can exploit data and instruction locality through careful dynamic scheduling decisions. The methods this thesis presents are not only specific to OLTP systems, but they can also benefit other types of applications that have concurrent requests executing a series of actions from a predefined set and face similar scalability problems on emerging hardware.

Adding limited reconfigurability to superscalar processors

Marc Epalza

For the last thirty years, electronics, at first built with discrete components, and then as Integrated Circuits (IC), have brought diverse and lasting improvements to our quality of life. Examples might include digital calculators, automotive and airplane control assistance, almost all electrical household appliances, and the almost ubiquitous Personal Computer. Application-Specific Integrated Circuits (ASICs) were traditionally used for their high performance and low manufacturing cost, and were designed specifically for a single application with large volumes. But as lower product lifetimes and the pressures of fast marketing increased, ASICs' high design cost pushed for their replacement by Microprocessors. These processors, capable of implementing any functionality through a change in software, are thus often called General Purpose Processors. General purpose processors are used for everyday computing tasks, and found in all personal computers. They are also often used as building blocks for scientific supercomputers. Superscalar processors such as these require ever more processing power to run complex simulations, video games or versatile telecoms services. In the case of embedded applications, e.g. for portable devices, both performance and power consumption must be taken into account. In a bid to adapt a processor to some extent to select applications, fully reconfigurable logic can greatly improve the performance of a processor, since it is shaped for the best possible execution with the available resources. However, as reconfigurable logic is far slower than custom logic, this gain is possible only for some specific applications with large parallelism, after a detailed study of the algorithm. Even though this process can be automated, it still requires large computing resources, and cannot be performed at run time. To reduce the loss in speed compared to custom logic, it is possible to limit the reconfigurability to increase the breadth of applications where performance can be improved. However, as the application space increases, a careful analysis and design of the reconfigurability is required to minimize the speed loss, notably when dynamic reconfiguration is considered. As a case study, we analyze the feasibility of adding limited reconfigurability to the Floating Point Units (FPUs) of a general purpose processor. These rather large units execute all floating point operations, and may also be used for integer multiplication. If an application contains few or infrequent instructions that must be executed by the FPU, this idle hardware only increases power consumption without enhancing performance. This is often the case in non-scientific applications and even many recent and detailed video games which make heavy use of hardware display accelerators for 3D graphics. In a fast multiplier such as can be found in the FPU of a high performance processor, the logic to perform multiplication is a large tree of compressors to add all the partial products together. It is possible to add logic to allow the reconfiguration of part of this tree as several extra Arithmetic and Logic Units (ALU). This requires a detailed timing analysis for both the reconfigurable FPU and the extra ALUs, taking into account effects such as added wires and longer critical paths. Finally, the algorithm to decide when and how to reconfigure must be studied, in terms of eciency and complexity. The results of adding this limited reconfigurability to a mainstream superscalar processor over a large set of compute intensive benchmarks show gains of up to 56% in the best case, with an average gain of 11%. The application to an idealized huge top processor still shows slightly positive average gains, as the limits of available parallelism are reached, bounded by both the application and many of the characteristics of the processor. In all cases, binary compatibility is maintained, allowing the re-use of all existing software. We show that adding limited reconfigurability to a general purpose superscalar processor can produce interesting gains over a wide range of applications while maintaining binary compatibility, and without large modifications to the original design. Limited reconfigurability is worthwhile as it increases the design space, allowing gains to apply to a larger set of applications. These gains are achieved through careful study and optimization of the reconfigurable logic and the decision algorithm.

EPFL2004

Processeur à haut degré de parallélisme basé sur des composantes sérielles

Ralph Hoffmann

Nowaday, the world of processors is still dominated by the RISC architectures, which foundations have been laid down in the 70's. The RISC concept may be summarized by one word : simplicity. With this concept, much simpler architectures are born, in particular from their instruction sets point of view. As a result, these architectures have a more efficient instruction decoding and smaller computing units which in turn provides the ability to have more of these units for the same price, a reduced clock per instruction ratio — a single cycle per instruction ideally — and increased clock frequencies. As time goes by, RISC architectures have shown outstanding performances, on one hand with the spectacular improvements of semiconductor technologies, and on the other hand with the use of large cache memories and with the development of new ways of execution such as speculative execution. Later developments have greatly altered the original spirit of the simplicity of the RISC concept. Current high performance processors are extremely complex and difficult to design. Moreover, semiconductor technologies begin to show serious problems ignored or neglected for a long time. In this thesis, we would like to introduce a new architecture. Two complementary aspects have been taken in consideration : the design of the processor's units (arithmetic operators, control logic, and so on) and the architectural model, the way the processing units are used. The first aspect has been addressed with an unusual and original approach which involves the use of the serial arithmetic principles. Serial arithmetic tends to reduce the hardware cost, enables higher clock rates, and shows interesting properties which will be developped later on. The research of an architectural model is driven by the same wish of simplicity, recurrent in this field, and will inevitably shift the complexity from the processor to the compiler. This simplification relies on two things : first, the way we think of the problem is inspired by the EPIC philosophy (Explicitly Parallel Instruction Computer), the latest offspring of the VLIW model which advocates the delegation of decisions from the hardware to the software. In one sentence, "the compiler decides, the hardware executes". Second, the way we act has been given by the TTA model (Transport Triggered Architecture), the last offspring of the MOVE model which not only removes from the processor the responsability to decide which processing unit to be used for each instruction (it's already the case in a VLIW processor), but also releases the processor from scheduling the data flows. In doing so, the processor is confined to provide a set of computing units, storage units and means of communication, and the compiler decides how to move the data. In this way, a part of the control logic is removed, communication resources may be fine-tuned and the compiler's code-optimization can be enhanced. With the combination of those elements, we wish to get an architecture which exhibits a better computing power/consumption ratio, which is more flexible, easier to developp and to evolve.

EPFL2004

Dynamically Matching ILP Characteristics Via a Heterogeneous Clustered Microarchitecture

Lei Chen

Applications vary in the degree of instruction level parallelism (ILP) available to be exploited by a superscalar processor. The ILP can also vary significantly within an application. On one end of the microarchitecture space are monolithic superscalar designs that exploit parallelism within an application. At another end of the spectrum are clustered architectures having many simple cores that can be clocked at a higher frequency than a comparable monolithic design. A disadvantage of the clustered design is the cost to transmit results between clusters which potentially limits the performance even in high ILP applications if instructions are not mapped carefully to minimize cross communication. In this paper, we propose an approach that incorporates the strengths of the prior two by clustering multiple integer ALUs in an asymmetric fashion. In one cluster, a 6-way out-of-order pipeline efficiently executes code having high ILP. In another cluster, a simpler, but deeper, 2-way pipeline running at twice the frequency speeds up regions of code having little ILP. We use the parallelism metrics gathered from the dynamic Data Dependence Tracking (DDT) mechanism to dynamically steer instruction windows to a cluster. We demonstrate that the heterogeneous cluster design can improve performance by up to 30% over a monolithic 8- way superscalar processor.

2004

Adding limited reconfigurability to superscalar processors

Marc Epalza

EPFL2004

Processeur à haut degré de parallélisme basé sur des composantes sérielles

Ralph Hoffmann

EPFL2004