Lecture

Optimizing Software: Locality & Scheduling

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-307: Introduction to multiprocessor architecture

Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce the essential technologies required to combine multiple ...

Description

This lecture by the instructor covers software optimizations focusing on locality, memory access, and scheduling strategies for parallel execution. It delves into cache hierarchy, latency considerations, cache miss models, coherence misses, and techniques to reduce true and false sharing. The lecture also includes examples like histogram computation, parallel work division, and matrix multiplication to illustrate optimization strategies. It emphasizes the importance of the locality principle, blocking for cache efficiency, and load balancing through dynamic work distribution. Additionally, it discusses loop optimizations, task queues for parallel processing, and functional parallelism for independent tasks.

Instructor

Babak Falsafi

Babak is a Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud, an industrial/academic consortium at EPFL investigating scalable data-centric technologies. He has made numerous contributions to computer system design and evaluation including a scalable multiprocessor architecture which was prototyped by Sun Microsystems (now Oracle), snoop filters and memory streaming technologies that are incorporated into IBM BlueGene/P and Q and ARM cores, and computer system performance evaluation methodologies that have been in use by AMD, HP and Google PerKit . He has shown that hardware memory consistency models are neither necessary (in the 90's) nor sufficient (a decade later) to achieve high performance in multiprocessor systems. These results eventually led to fence speculation in modern microprocessors. His latest work on workload-optimized server processors laid the foundation for the first generation of Cavium ARM server CPUs, ThunderX. He is a recipient of an NSF CAREER award, IBM Faculty Partnership Awards, and an Alfred P. Sloan Research Fellowship. He is a fellow of IEEE and ACM.

Official source

Ontological neighbourhood

Computer engineering

Computer architecture: Topics in computer architecture

Related concepts (32)

Cache (computing)

In computing, a cache (kæʃ ) is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests that can be served from the cache, the faster the system performs.

Locality of reference

In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference locality - temporal and spatial locality. Temporal locality refers to the reuse of specific data and/or resources within a relatively small time duration. Spatial locality (also termed data locality) refers to the use of data elements within relatively close storage locations.

Cache hierarchy

Cache hierarchy, or multi-level caches, refers to a memory architecture that uses a hierarchy of memory stores based on varying access speeds to cache data. Highly requested data is cached in high-speed access memory stores, allowing swifter access by central processing unit (CPU) cores. Cache hierarchy is a form and part of memory hierarchy and can be considered a form of tiered storage. This design was intended to allow CPU cores to process faster despite the memory latency of main memory access.

Loop optimization

In compiler theory, loop optimization is the process of increasing execution speed and reducing the overheads associated with loops. It plays an important role in improving cache performance and making effective use of parallel processing capabilities. Most execution time of a scientific program is spent on loops; as such, many compiler optimization techniques have been developed to make them faster. Since instructions inside loops can be executed repeatedly, it is frequently not possible to give a bound on the number of instruction executions that will be impacted by a loop optimization.

Program optimization

In computer science, program optimization, code optimization, or software optimization, is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be optimized so that it executes more rapidly, or to make it capable of operating with less memory storage or other resources, or draw less power. Although the word "optimization" shares the same root as "optimal", it is rare for the process of optimization to produce a truly optimal system.

Related lectures (64)

Optimizing Software: Software Optimizations

Covers software optimizations to improve program performance by maximizing cache hits and optimizing work distribution.

Optimizing Software: Software Optimizations & Work Distribution

Covers software optimization, cache efficiency, parallel scheduling, and work distribution strategies for fast parallel programs.

Cache Memory

Explores cache memory design, hits, misses, and eviction policies in computer systems, emphasizing spatial and temporal locality.

Rescuing Data Center Processors

Explores challenges and solutions for data center processors, focusing on efficiency, cache issues, branch prediction, and architectural optimizations.

Challenges in High-Level Synthesis: Optimizing Loop Constructs