Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

optimization
theoretical cs

What is speculative execution?

Sahar Moueen

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

Speculative execution is an optimization technique that uses unused processing cycles. Programs are stacked on for input-output operations, so it starts prefetching data for future needs by executing ahead of their executions.

Out-of-order execution (OoOE) and concurrent processing are used in speculative execution to predict and retrieve data that might need in the future.

Working

For instance, the application reads three non-resident data pages distributed across three discs. When regular execution stalls on I/O requests, execution would proceed speculatively. The original disc request will complete, and then normal execution will start again. Then, all of the data accesses will be handled in the main memory, decreasing the application’s execution time in half.

In the illustration below, "1." shows how execution for a hypothetical application would typically proceed.

Similarly, "2." demonstrates how the application’s execution might depend on the speculative execution strategy. Speculative execution might be able to start prefetching, while conventional execution pauses on its first I/O request.

I/O stall time decreased via a speculative execution strategy

Note: It is important to remember that speculative execution will not always work. For example, it won’t be effective on systems with a fully utilized CPU, memory, or storage.

Importance

When an application requires information not currently in memory, it will send a disk request and halt while waiting for the request to be processed. To avoid delay, work is completed before it is known whether it is required.

Performance can be improved by reducing latency Time required to transmit data from one point to anotherand exhibiting more parallelismIt means parallel execution of task across multiple processors by executing instructions speculatively. The drawback is that the results of speculative execution could be discarded if it turns out that the given instructions weren’t necessary.

Techniques

The following two techniques are used for speculative execution:

Eager evaluation

Both sides of the conditional branch are evaluated in eager execution, a form of speculative execution, but the outcomes are only recorded if the condition is satisfied. Theoretically, eager execution would function as perfect as branch prediction if resources were not restricted. Eager execution should be used with caution when resources are few.

Predictive evaluation

A form of speculative execution known as predictive execution occurs when an outcome is predicted, and execution moves forward along the anticipated course until the actual result. If the forecast is accurate, the anticipated execution may proceed, but if it is inaccurate, it must be rolled back and re-executed.

Applications

Speculative execution has a wide variety of applications in the area of the following:

  • Branched prediction in pipelined processors.
  • Optimistic concurrency control in databases.
  • Prefetch cache memory and files' data.
  • Value Prediction.

RELATED TAGS

optimization
theoretical cs

CONTRIBUTOR

Sahar Moueen
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring