How Hierarchical Cache and Memory Locality Affect Performance in Multithread Systems

n my last article, I pointed out the importance of knowledge of how the computer handles information and how it translates it into binary language.

That said, I will go in this article, make a brief deepening in the relevance of cache in software development and how it can affect positively or negatively depending on the code you write on a daily basis.

As I have already addressed and reiterate again: the increase in abstraction layers and automation provided by modern compilers do not eliminate the need to understand the complex aspects of development. On the contrary, this technical layer remains critical, even in high-level languages.

It is not just about demanding advanced knowledge in Assembly or very low level (although this adds value). The center point is that languages such as C++, Rust, Go and java still require active attention to memory management, resource allocation and optimizations. Mastering these mechanisms allows:

1. Prevention leaks and performance bottlenecks
2. Control the precision over the life cycle of objects
3. Agile diagnosis of problems that abstractions conceal

Those who develop this expertise transcend the dependence of frameworks or automated tools. It is able to solve deep technical challenges, precisely those that impact scalability, security and efficiency.

John Von Neumann Architecture

Since the invention of computer architecture created by John Von Neumann, all processors have the same architecture created by him in 1945. Clearly, computer organization has changed much of the past century, but its architecture has remained the same. After all, you may be wondering the difference between the two and it is common for people to confuse both sometimes.

Architecture is defined by the logical and structural concept of the components of a computer system, that is, how the components of the hardware interact with each other to execute programs. The organization refers to the physical and operational implementation of the architecture, that is, how the physical components of the system are designed and connected to meet the needs of the architecture.

Now that we understand the concept of architecture and organization, we need to know the structure of the components that composes a computer or electronic device that we use in our daily lives.

We start with the Main Memory, which in the current computers, can be represented by RAM (volatile memory) and the hard disk (non-volatile memory).

RAM stores temporary data from open programs and applications on the computer, but when the computer is turned off, data from that memory is lost. The hard disk (HD or SSD for example) stores the data permanently, so that RAM can query this information when opening a software or performing an instruction.

I/O (Input and Output) devices are established as the components that move data between the computer and external environment. Among the main ones are:

• USB Ports
• Audio Connectors (for headphones, microphones and speakers)
• Ethernet ports (for network connections)
• Display Doors (HDMI, DisplayPort)

Finally and not least we have the CPU (Central Processing Unit). There are 5 main functions that the processor (CPU) is responsible for:

• Stores temporary cached data to increase performance and efficiency
• Sort, decode and process the instructions passed by CU(I will detail further in the article) so that later encrypt and send the information to memory and I/O components.
• Performs fixed point and floating point arithmetic operations.
• Manages traffic of instructions between the components of each core of the CPU to avoid bottlenecks or loss of performance.

Inside the CPU

There are 2 types of processors, single-core (which have only 1 core) and multi-core ones (which have 2 or more cores), however, I will address in this article only the multi-core processors, taking into account that most CPUs today from practically any domestic electronic device has more than 2 processing cores. Remembering that the variation in the construction of a processor varies according to the manufacturer, but the images presented will give you an idea of the general structure of the processors.

Among the main components of a single-core processed are:

• Registers
• CU (Control Unit)
• ALU (Arithmetic and Logic Unit)
• System Buses

Registers are a special type of memory that temporarily stores and transfers data from instructions within the CPU. On the contrary, from the cache, this type of memory has a slightly more limited storage capacity, but faster than the memory cache.

CU, also called the Control Unit, is responsible for interpreting the instructions stored in memory and sending necessary control signals for other components (such as ALU, Memory, and I/O Units) to perform corresponding operations.

ALU, which in Portuguese means Logic and Arithmetic Unit, has the function that in its name says, perform mathematical operations within the CPU, such as addition, subtraction, multiplication and division. In addition to arithmetic operations, ALU also performs logical operations (AND, OR, NOT, XOR, NOR, NAND) and comparison operations (“Minor” that”, “Equal to”).

Finally we have the buses, which provide the interconnection between the CPU components.

For Multi-Core processors, its architecture includes:

• L3 Caches
• 2 or more colors (cores)
• Other secondary components such as ALU, registers and etc, but depending on the type of manufacturer

Caches L3 are components that store data often used between the cores of the processor, increasing the efficiency of the processor. It has this name because there is a hierarchy of caches (L1, L2 and L3) within the CPU and the letter “L” represents the word “Level”. This hierarchical organization exists to facilitate and optimize the cost of processing and storage of instructions and data within the processor. In addition, L3 Caches are slower than L1 and L2 Caches and have a storage capacity between 1MB-8 MB.

Core is an individual processing unit on a processor chip. An individual core can be equivalent to a single core processor, meaning it is possible to conclude that a multi-core processor is nothing more than multiple single-core processors together on a single CPU chip.

What is the role of each Core?

Among the main components that form each core includes:

• FPU (Floating Pointing Unit): Conducts floating-point operations
• ALU (Arithmetic Logic Unit): Performs entire and logical arithmetic operations
• ISU (Instruction Sequence Unit): Determines the sequence of instructions that will be processed
• IFU (Instruction Fetch Unit): Search for the instructions determined by ISU in cache memory or, if necessary, in RAM.
• IDU (Instruction Decode Unit): Decodes the instructions that the IFU has placed in the Buffers.
• RU (Recovery Unit): Keeps a copy of the state of the registers in case of hardware failure.
• COP (Dedicated Co-Processor): Responsible for data compression and encryption functions.
• L1 Cache: Cache faster but smaller in terms of storage (between 16kb and 128kb) than L2 Cache. It is responsible for storing frequently used. In addition, it is the cache considered a priority by the other components in case of data queries.
• L2 Cache: Slower but larger cache in terms of storage (between 128kb and 2mb) than the L1 Cache. In addition, it is considered a secondary cache that is used if L1 does not have enough data for query, thus increasing the processor performance.

You will probably find different organizations in the structure of a CPU, because each manufacturer has a different strategy in the construction of the same and in addition to chips for home computers, there are also other types of system, such as network computing, embedded systems, parallel processing systems, data storage system and among others.

In any case, the computer architecture (created by John Von Neumann in 1945) remains the same, that is, it has a logical design and how the components have interacted and communicated with each other since the last century.

Buffers, Cache and Ram are the same thing?

During this article, I mentioned some types of memory that are present in the architecture of a computer, including Buffers, Cache, and Ram. After all, if everyone stores data, what is the difference and function of each in the processing and storage of data in the CPU?

Buffers are present in several components within a motherboard, including the IFU (Instruction Fetch Unit) mentioned above. In this context, buffers deal with the flow of data and instructions within each core to avoid bottlenecks and processor performance issues. For example, imagine that you are in a big city with many street and avenues. There are many cars (data) trying to move between different parts of the city (computer components).

Now, imagine that the traffic coordinators are positioned between important intersections (these ones would be the buffers). They have the task of controlling the flow of cars, ensuring that the circulation is organized and efficient. Without these coordinators, cars (data) could accumulate on the streets, causing congestion, which in the case of computer components, there would be an overload with an excessive flow of data at the same time. In addition, it is important to emphasize that the data is not stored within the buffer, but rather often changes with each cycle (clock) of the processor.

Regarding the Caches, they store data and keep it for more processor cycles so that the components access the data more efficiently. Among the most used is Cache L1, L2 and L3 as previously mentioned.

RAM memory is responsible for storing temporary data not often used by the CPU. Remember that RAM memories are slower than caches and buffers.

Cache Location and its Impact on Performance in Multi-Thread Systems

The underlying principle of cache memory is the reference location, since, if the data is accessed once, they are likely to be accessed again in the near future. By storing this data in the cache, the system significantly reduces the time it takes to access it, resulting in a noticeable improvement in overall performance.

When the CPU needs to recover data, it initially checks the cache memory. If the requested data is present in the cache, this is called “hit cache”. Consequently, the CPU can quickly recover the cache data by bypassing the slower main memory.

On the other hand, if the required data is not found on the CPU, it results in a “cache loss.” In such cases, the CPU must access the main memory to obtain data.

The decision-making process about what data to keep in the cache and which ones are needed to discard is defined by a cache policy. Common policies include the Least Recent Use (LRU), which discards data that has remained unused for longer, and the Most Recent Use (MRU), which prioritizes the removal of the data accessed most recently.

Larger storage is not equivalent to higher performance

Cache memory plays a crucial role modern computing systems, providing quick access to data more accessed by nearby components. However, contrary to what intuition suggests, increasing the cache size does not translate into better performance. The relationship between caching and caching speed involves complex offsets between physical constraints, access patterns, and economic considerations.

Delay in signal propagation

One of the main physical limitations of caches greater storage is the increase that data transmission signals need to travel. As the size increases, the physical dimensions of the memory cache expand accordingly, resulting in longer signal paths. This physical reality directly impacts performance because electrical signals can only travel to a limited speed.

Limitation on Clock Speed

Larger caches also introduce synchronization challenges with the clock speed of the CPU. The L1 Cache, which is the closest to a processor core, needs to operate in sync with the CPU to provide immediate access to the most used data. If the L1 Cache becomes much larger in terms of storage, the increase in access latency would force the reduction in the maximum clock rate in the processor, compromising performance.

Concerns about energy consumption

Caches of higher storage consume more energy, which is a critical constraint in many contexts of computing. This higher energy consumption becomes particularly problematic in mobile and embedded systems, where energy efficiency is a major priority. Higher energy demands in larger caches can lead to an increase in heat generation, requiring more robust cooling solutions and further increasing the cost of system complexity. In many cases, the benefit in performing a slightly larger cache does not justify the energy cost generated by it.

• Cache Memory - Definition and general information - Redis
• Von Neumann architecture - The CPU - Eduqas - GCSE Computer Science Revision - Eduqas - BBC Bitesize