Parallel Execution

Overview

aelf analyzes the static state of transactions and assesses the impacted data range of each transaction. As illustrated in Figure 9.0, multiple transactions without read/write conflicts can then be processed in parallel, without affecting the output of each transaction. During the process of block formation, nodes assign transactions to different groups based on the mutex of the transactions. Transactions within a group will be processed in sequence, while all groups will be processed simultaneously.

Figure 9.0. Parallel transactions processing within a block

There are special transactions that cannot be processed in parallel because they impacted data ranges change while other transactions are being processed. For these circumstances, nodes will prioritize transactions that can be processed in parallel. With sufficient transaction fees, these special transactions in a nonparallel group will be processed in sequence. Otherwise, nodes can reject these transactions. It is to be noted that, when a faulty node accepts a transaction that cannot be processed in a parallel and time-consuming manner, the probability that other nodes reject this Block increases.

Amdahl's law is an empirical rule in computer architecture named after Computer Scientist Gene Amdahl that gives the theoretical speedup in efficiency when using parallel processing. Think about a program that runs on a single processor. In terms of the execution time, $f$ is the proportion of the execution time that the part benefiting from improved resources originally occupied, so $1-f$ is the proportion of execution time that is fixed for sequential processing. If there are $m$ (numbers) of processors that run in parallel, then the theoretical speedup of this program will be calculated as follows:

$SpeedUp_{Amdahl} \coloneqq \cfrac{1}{(1-f) + \cfrac{f}{m}}$

Two major conclusions are conducted:

• (1) Speedup hardly improves when $f$ is at minimum.

• (2) As m rises to the maximum, speedup is limited by $1/(1-f)$.

Amdahl's law is a fixed-size mode, which means it will solve problems of a fixed size with a fixed proportion of execution in parallel.

Most Blockchain transactions are not correlated. Using Amdahl’s law, data execution can be greatly sped up. However, most present Blockchain systems execute in sequence, and all nodes carry out the same set of computing. This wastes resources and hinders transaction speed. EVM, for instance, does not only process transactions sequentially, but also has requirement for gas fees, resulting in extremely low performance efficiency.

Figure 9.1 Grouping Transactions

To solve complex blockchain problems, low-speed transactions are simply not a viable option. aelf aims to build a blockchain system with high on-chain Transactions Per Second (TPS) through parallel processing. The key here is to separate transaction data and computational dependency, which solves data hazard issues. We could refer to the architecture of Intel micro-processor, where a reservation station segregates electronic circuit dependency, employing techniques like register renaming to address the significant data hazards that commonly arise in Read After Write (RAW), Write After Write (WAW), and Write After Read (WAR) scenarios, allowing for parallel execution of Arithmetic Logic Units (ALUs).

AI Based Parallel Execution Scheduling

The aelf Parallel Execution Scheduler (aPES) was conceived with the purpose of addressing scheduling challenges in parallelized systems. During regular internal testing, aelf effectively segregates computational and data dependencies within the Blockchain from the memory pool. aPES boasts several key features, including pretreatment such as predicting computing time spans, pre-indexing code segments suitable for parallel processing, initializing pipelines, and executing parallel tasks across multiple dimensions.

Efficient task scheduling across resources is crucial for enhancing execution speed, reducing duration, and mitigating various challenges such as communication delays, costs, and priority conflicts.

In our ongoing efforts to enhance aPES technology, we are integrating AI to further elevate its capabilities. This innovative approach begins with harnessing neural network prediction to estimate the time required for completing ongoing transactions on computational resources. Furthermore, we recognize the importance of considering computational resource availability alongside transaction durations, thereby addressing user concerns regarding transaction execution costs. To optimize resource allocation, we implement a two-stage process: first, employing a clustering method, and then utilizing the genetic algorithm's meta-heuristic. This comprehensive strategy enables us to improve population production, enhance resource utilization efficiency, and ultimately enhance the overall execution time of tasks. You may understand more about this technique in the paper here.

aelf’s pipeline is also an important method to increase speed. It has been widely adopted for cases such as CPU and meta function (map, aggregate first, and contains) processing. This set of Turing incomplete language is perfect for processing data streams (or simple transaction streams). Parallel processing functions and context free/immutable computing will make full use of cores and nodes.

In general, parallel processing is a comprehensive strategy to significantly increase the speed of Blockchain transactions.