Pipelining and the Function Call Stack
The CPU of an embedded device must process sensor inputs and control calculations within the required time under a limited clock frequency.
This is because there are many situations where executing instructions one by one in order is not fast enough.
This article covers two topics: pipelining, which improves processing efficiency, and the stack, which is the foundation of function calls. Since both are involved in actual design decisions, it is worth understanding at least an overview of how they work.
- Why Do CPUs Need “Speed-up Mechanisms”?
- Pipelining - Improving Efficiency with an “Assembly Line” of Instructions
- The Stack - A Mechanism Supporting Function Calls and Returns
- Understanding CPU Operation Supports the Quality of Embedded Software
Why Do CPUs Need “Speed-up Mechanisms”?
CPUs have limited processing capability when relying solely on sequential instruction-cycle execution. Many embedded devices are limited to clock frequencies ranging from several tens to several hundreds of MHz and must process sensor inputs and control calculations within a fixed cycle.
For example, if motor control requires a control cycle of 10 kHz, the time allowed for each operation is 1 ÷ 10,000 = 100 microseconds. This is a surprisingly tight value, and it is not uncommon for processing to fail to fit within the cycle if instructions are simply processed one at a time in sequence.
To cope with these constraints, CPUs are equipped with mechanisms that supplement sequential execution and improve processing efficiency.
Pipelining - Improving Efficiency with an “Assembly Line” of Instructions
Pipelining is a mechanism that divides each step of an instruction cycle into independent units and processes multiple instructions in parallel, like an assembly line. By keeping hardware resources that were not used in sequential execution constantly active, the processing efficiency of the CPU can be greatly improved.
Since this mechanism affects the processing time of embedded software, we will explain it starting from the basic concept.
Basic Concept of Pipelining
The three steps of fetch, decode, and execute are handled by independent hardware units. In the sequential execution method, the next instruction is not fetched until one instruction is completed through execution, so the fetch unit and decode unit are in a standby state during that time. In other words, most of the hardware spends a long time waiting, leaving room for improvement.
In pipelining, the moment the fetch unit retrieves instruction A and passes it to the decode unit, it can immediately start fetching instruction B.
Once the decode unit finishes decoding instruction A, it starts working on instruction B, while the fetch unit retrieves instruction C. In this way, each unit continues to operate without rest. This parallel operation brings the system closer to a state where one instruction is completed per clock cycle.
In addition, the Arm Cortex-M3, which is widely used in embedded microcontrollers, also implements this three-step pipeline. If the pipeline is not interrupted, the design is such that calculation results are output every cycle. In reality, however, there are situations where this flow stops depending on the instructions.
When the Pipeline Stalls - Hazards and Countermeasures
The flow of instructions through the pipeline can be delayed due to dependencies between instructions. This phenomenon is called a pipeline hazard. Typical examples include data hazards and control hazards.
A data hazard occurs when the calculation result of a previous instruction is required by the immediately following instruction. In cases where the result of an addition instruction is stored in register R1 and the next instruction refers to R1, subsequent instructions cannot proceed until the addition result has been stored.
The pipeline pauses here, and this standby state is called a stall. Although easily overlooked, register dependencies between consecutive instructions occur surprisingly often in code.
A control hazard is triggered by a conditional branch instruction. Since whether the branch is taken or not is not determined until the calculation result is available, the pipeline tentatively continues to fetch the next instruction. However, if the branch is taken, those instructions must be discarded, and instructions must be fetched again from the branch destination.
To suppress this loss, the Cortex-M3 is equipped with a branch speculation function that calculates the branch destination in advance. Since either hazard can make processing-time estimates inaccurate, they should be considered during the design stage. In addition, writing code that minimizes conditional branching makes it easier to estimate processing time.
The Stack - A Mechanism Supporting Function Calls and Returns
The stack is a storage area used to temporarily save and restore register values and the program counter during function calls or interrupt processing.
This section explains the structure of the stack, which supports the operation of embedded software behind the scenes.
What Is a Stack? – Last-In, First-Out (LIFO) Storage Area
A stack is a LIFO (Last-In, First-Out) data area allocated in RAM. New data is written using a PUSH instruction as if stacking it on top, and when retrieving data, a POP instruction retrieves the most recently stacked data first.
A dedicated register called the stack pointer (SP) manages the location where this data is saved. Executing a PUSH advances the SP address, and executing a POP moves it back. In a 32-bit CPU, it is common for the SP to move by 4 bytes with a single PUSH.
Although it may seem unremarkable at first glance, this mechanism allows data to be saved and restored accurately without the programmer having to directly specify addresses. This knowledge is a prerequisite for understanding the function call operations explained next.
What Happens in the Stack During a Function Call
The moment a program calls a function, the CPU first PUSHes the return address (the current value of the program counter) onto the stack. Next, it saves the contents of the registers used by the caller. Furthermore, local variables within the called function are allocated on the stack, and the SP advances by that amount.
When the function processing ends, this flow is wound back in reverse order. The local variable area is released, the registers are restored, and the return address is restored to the program counter, allowing execution to resume from the next instruction of the caller. The fact that calling and returning form a pair aligns well with the LIFO structure.
In addition, if a nested structure is used where another function is called from within a function, these PUSH/POP operations stack up multiple times. The deeper the nesting goes (three or four levels), the more stack space is consumed. Therefore, in environments like embedded systems where only a few hundred bytes of stack area can be allocated, the depth of the call hierarchy acts as a design constraint.
Understanding CPU Operation Supports the Quality of Embedded Software
Understanding the operating characteristics of the pipeline makes it possible to estimate processing time while considering stalls caused by hazards. Even when actual measured values deviate from theoretical values in code with many branches, whether you can identify the cause depends on having this knowledge.
Understanding the stack directly relates to preventing overflows. In embedded environments, it is not uncommon for the stack area to be limited to a few hundred bytes to several KB.
In such environments, if deep nested function calls and local variable declarations of large arrays overlap, the stack may overflow beyond the allocated area, potentially causing abnormal program operation. In addition, stack overflows often occur only on specific call paths, making them troublesome as they easily slip through normal testing.
For both, investigating after a problem occurs is too late. Making estimates and understanding constraints during the design phase are essential to ensuring quality.
In practice, it is often unrealistic to estimate everything accurately when designing a system. When selecting hardware, it is advisable to allow some margin for memory and processing speed.
