Written by: PREDA Source: chainfeeds
Looking at the history of computer parallelism: the first level of parallelism is instruction-level parallelism. Instruction-level parallelism was the main way to improve the performance of the architecture in the last 20 years of the 20th century. Instruction-level parallelism can improve performance while maintaining binary compatibility of programs, which is particularly popular among programmers. There are two types of instruction-level parallelism. One is time parallelism, that is, the instruction pipeline. The instruction pipeline is like the assembly line of a factory producing cars. The car production factory will not wait until one car is assembled before starting the production of the next car, but will produce multiple cars at the same time in multiple processes. The other is spatial parallelism, that is, multiple launches, or superscalar. Multiple launches are like a multi-lane road, and out-of-order execution allows overtaking on multiple lanes. Superscalar and out-of-order execution are often used together to improve efficiency. After the emergence of RISC in the 1980s, the development of instruction-level parallelism reached a peak in the following 20 years. After 2010, there was not much room for further exploration of instruction-level parallelism. The second level of parallelism is data-level parallelism, which mainly refers to the vector structure of single instruction stream multiple data stream (SIMD). The earliest data-level parallelism appeared on ENIAC. In the 1960s and 1970s, vector machines represented by Cray were very popular, from Cray-1, Cray-2, to later Cray X-MP and Cray Y-MP. Until Cray-4, SIMD was silent for a while, but now it has begun to recover and is used more and more. For example, the AVX multimedia instructions in X86 can use 256-bit channels to perform four 64-bit operations or eight 32-bit operations. As an effective supplement to instruction-level parallelism, SIMD has played an important role in the field of streaming media. It was mainly used in special-purpose processors in the early days, and now it has become a standard feature of general-purpose processors.
The third level of parallelism is task-level parallelism. Task-level parallelism exists in large numbers in Internet applications. Task-level parallelism is represented by multi-core processors and multi-threaded processors, and is the main method for improving performance in current computer architectures. Task-level parallelism has a large parallel granularity, with hundreds or more instructions in one thread.
From the perspective of the development of parallel computing, blockchain is now in the process of transition from the first level to the second level. Mainstream blockchain systems usually adopt single-chain or multi-chain architectures. Single-chain, such as the common Bitcoin and Ethereum, has only one chain in the entire system, and each node in the chain executes exactly the same smart contract transactions and maintains a completely consistent on-chain state. In each blockchain node, smart contract transactions are usually executed serially, resulting in low throughput of the entire system.
Some high-performance blockchain systems that have emerged recently, although using a single-chain architecture, also support parallel execution of smart contract transactions. Thomas Dickerson and Maurice Herlihy of Brown University and Yale University first proposed a parallel execution model based on the STM (Software Transactional Memory) method in their PODC’17 paper. This method uses optimistic parallelism to execute multiple transactions in parallel. If a transaction encounters a state access conflict during the parallel execution, the state is rolled back through STM, and then the state-conflicting transactions are executed serially. This type of method has been applied to many high-performance blockchain projects, including Aptos, Sei, and Monad. Correspondingly, another parallel execution model is based on pessimistic concurrency, that is, before a transaction is executed in parallel, it is necessary to detect whether the state accessed by the transaction conflicts. Only transactions without conflicts can be executed in parallel. This type of method usually adopts a pre-compute method, using program analysis tools to perform static analysis on the smart contract code and construct state dependencies, such as a directed acyclic graph (DAG). After concurrent transactions are submitted to the system, the system determines whether the transaction can be executed in parallel based on the state that the transaction needs to access and the dependencies between the states. Only transactions that have no state dependencies between each other will be executed in parallel. This type of approach has been applied to high-performance blockchain projects such as Zilliqa (CoSplit version) and Sui. The above parallel execution models can significantly improve the system throughput. These two solutions correspond to the instruction-level parallelism mentioned above. However, there are two problems with these works: 1) scalability issues and 2) parallel semantic expression issues, which we will elaborate on below.
We will use the typical technical solutions of Solana and Monad projects as examples to disassemble their parallel architecture designs, including parallelization classification, data dependencies, and other key indicators that affect parallelism and TPS.
Solana
At a high level, Solana's design philosophy is that blockchain innovation should develop with the advancement of hardware. As hardware continues to improve according to Moore's Law, Solana aims to benefit from higher performance and scalability. Solana co-founder Anatoly Yakovenko originally designed Solana’s parallelized architecture over five years ago, and today, parallelism as a blockchain design principle is spreading rapidly.
Solana uses Deterministic Parallelization, which comes from Anatoly’s past experience with embedded systems, where developers typically declare all state up front. This allows the CPU to understand all dependencies, allowing it to prefetch necessary portions of memory. The result is optimized system execution, but again, it requires developers to do extra work up front. On Solana, all memory dependencies of a program are required and stated in constructed transactions (i.e., access lists), allowing the runtime to efficiently schedule and execute multiple transactions in parallel.
The next major component of the Solana architecture is the Sealevel VM, which supports processing multiple contracts and transactions in parallel based on the number of cores a validator has. Validators in a blockchain are network participants responsible for verifying and confirming transactions, proposing new blocks, and maintaining the integrity and security of the blockchain. Because transactions declare up front which accounts require read-write locks, the Solana scheduler is able to determine which transactions can be executed concurrently. Because of this, when validating, "block producers" or leaders are able to sort through thousands of pending transactions and schedule non-overlapping transactions in parallel.
Monad is building a parallel EVM layer 1 with Turing completeness. What makes Monad unique is not only its parallelization engine, but also the optimization engine they built under the hood. Monad takes a unique approach to its overall design, incorporating several key features including pipes, asynchronous I/O, separation of consensus and execution, and MonadDB.
Similar to Sei, Monad blockchain uses Optimistic Concurrency Control (OCC) to execute transactions. Concurrent transaction processing occurs when multiple transactions exist in the system at the same time. This transaction method has two phases: execution and verification.
During the execution phase, transactions are processed optimistically and all reads/writes are temporarily stored in transaction-specific storage. After this, each transaction will enter the verification phase, where the information in the temporary storage operation is checked against any state changes made by previous transactions. Transactions run in parallel if they are independent. If one transaction reads data modified by another transaction, a conflict arises.
A key innovation of Monad design is pipelining with a slight offset. This offset allows more processes to be parallelized by running multiple instances simultaneously. Therefore, pipelines are used to optimize many functions, such as the state access pipeline, the transaction execution pipeline, the pipeline within the consensus and execution, and the pipeline of the consensus mechanism itself, which corresponds to washing, drying, folding clothes and putting them in the closet in the figure below.
Monad, transactions are ordered linearly within the block, but the goal is to reach the final state faster by leveraging parallel execution. Monad uses an optimistic parallelization algorithm to design the execution engine. Monad's engine processes transactions simultaneously and then analyzes them to ensure that the results will be the same if the transactions are executed one after another. If there is a conflict, re-execution is required. The parallel execution here is a relatively simple algorithm, but combining it with the other key innovations of Monad is what makes this approach novel. One thing to note here is that even if re-execution occurs, it is usually cheap because the inputs required by the invalid transaction are almost always retained in cache, so it will be a simple cache lookup. The re-execution will definitely succeed because you have already executed the previous transactions in the block.
In addition to delaying execution, Monads also improve performance by decoupling execution and consensus, similar to Solana and Sei. The idea here is that if you relax the condition for execution to complete when consensus is complete, you can run both in parallel, giving both extra time. Of course, Monad handles this situation with a deterministic algorithm to ensure that one doesn't run too far ahead to catch up.
Whether optimistic or pessimistic parallel execution is adopted, the above system uses shared-memory as the underlying data model abstraction, that is, no matter how many parallel units there are, the parallel units can obtain all data (here refers to all on-chain data of the blockchain), and the state data can be directly accessed by different parallel execution units (that is, all on-chain data can be directly read and written by parallel units). Blockchain systems that use shared-memory as the underlying data model usually have concurrency limited to a single physical node (Solana), and the concurrency of each physical node is limited by the computing power of the node, that is, the number of physical threads (assuming that each thread supports a virtual machine).
This intra-node parallel approach only requires modifying the architecture of the smart contract execution layer, and does not require modifying the logic of the system consensus layer, which is very suitable for improving the throughput of single-chain systems. Therefore, since there is no sharding of data storage, each node in the blockchain network still needs to execute all transactions and store all states. At the same time, compared to the shared-nothing architecture that is more suitable for distributed expansion, these systems that use shared-memory as the underlying data model abstraction cannot achieve horizontal expansion of processing power, that is, the expansion of system state storage and execution capacity by increasing the number of physical machines, thus failing to fundamentally solve the scalability problem of blockchain.
So is there a ready-made solution?
Before introducing PREDA, we would like to raise a natural question: Why use parallel programming? In the 1970s, 1980s and even part of the 1990s, we were very satisfied with single-threaded programming (or serial programming). You can write a program to complete a task. After the execution, it will give you a result. The task is completed and everyone will be happy! Although the task is completed, if you are doing a particle simulation that requires millions or even billions of calculations per second, or processing images with tens of thousands of pixels, you will want the program to run faster, which means you need a faster CPU.
Before 2004, CPU manufacturers IBM, Intel, and AMD could provide you with faster and faster processors, with processor clock frequencies gradually increasing from 16 MHz, 20 MHz, 66 MHz, 100 MHz, to 200 MHz, 333 MHz, 466 MHz... It seemed that they could continue to increase the speed of the CPU, that is, they could continue to improve the performance of the CPU. But by 2004, it was obvious that the trend of increasing CPU speed could not continue due to technological limitations. This requires other technologies to continue to provide higher performance. The solution of CPU manufacturers is to put two CPUs in one CPU, even if both CPUs work slower than a single CPU. For example, two CPUs (manufacturers call them cores) running at 200 MHz can perform more calculations per second (that is, intuitively 2×200 > 300) than a single CPU running at 300 MHz.
The dream-like story of "single CPU with multiple cores" has become a reality, which means that programmers must now learn parallel programming methods to take advantage of the two cores. If a CPU can execute two programs at the same time, then programmers must write two programs. But does this translate into running the program twice as fast? If not, then our idea of 2×200 > 300 is problematic. What happens if one core doesn't have enough work? That is, only one core is really busy, while the other core is doing nothing? In this case, it's better to use a single core at 300 MHz. After the introduction of multiple cores, many similar problems become very prominent, and only programming can effectively utilize these cores.
In the figure below, we imagine Bob and Alice as two gold diggers, and gold mining requires four steps:
Driving to the mine
Mining
Loading ore
Storing and polishing
This is also the essence of Solana's parallel VM, core sharing.
Core Sharing
The final design element of Solana is "pipelining". Pipelining occurs when data needs to be processed through a series of steps and different hardware is responsible for each step. The key idea here is to take data that needs to run serially and parallelize it using pipelines. These pipelines can run in parallel, and each pipeline stage can process different batches of transactions. The higher the processing speed of the hardware (mining car loading capacity), the higher the parallelization throughput. Today, Solana's hardware node requirements have left its node operators with only one choice - data centers, which brings efficiency but deviates from the original intention of blockchain.
After upgrading the mining car, because the mining capacity cannot keep up, the mining car is often not fully loaded. So Bob spent a high price to purchase a mining machine to improve the efficiency of mining (execution unit upgrade). The same 15 minutes can produce 10 ore, but because the ore grinding work is still done by hand as before, more ore produced per unit time cannot be converted into more gold, and more ore is squeezed in the warehouse; this example shows what happens when access to memory is the limiting factor of our program execution speed. It doesn't matter how fast we process data (i.e. how fast the core runs). We will be limited by how fast we can get the data. Slow I/O speeds will seriously bother us because I/O is the slowest part of the computer, and asynchronous reading of data will become critical. Even if Bob has a mining machine that can mine 10 minerals in 15 minutes, if there is memory access contention, they will still be limited to 2 minerals every 15 minutes. Existing parallel blockchain solutions to this problem are divided into two camps - pessimistic execution and optimistic execution. The former requires that the dependencies of data states be clearly defined before data is written and read, which requires developers to make upfront static control dependency assumptions, which often deviate from reality in the field of smart contract programming. The latter makes no assumptions or restrictions on writing data and rolls back if a conflict occurs. Take Monad's optimistic execution scheme as an example: the reality is that most of the workload is transaction execution, and there are not as many scenarios that occur in parallel as imagined. The following figure shows the source types of Ethereum's daily Gas Fee consumption; you will find that although this distribution is not as high as the popular smart contracts, in fact, different types of transactions are not evenly distributed. The optimistic execution of parallel logic is feasible in the Web2 era, because a large part of the requests of Web2 applications are access, not modification; for example, Taobao and Douyin, you don't have many opportunities to modify the status of these apps. However, in the Web3 field, it is just the opposite. Most smart contract requests are just to modify the status - update the ledger, which actually brings more rollbacks than expected, making the chain unavailable.
So the conclusion is that Monad can indeed achieve parallelism, but the degree of parallelism (Concurrency) has a theoretical upper limit, which is between 2 and 3 times, not the advertised 100K. Secondly, this upper limit cannot be expanded by adding virtual machines, that is, there is no way to achieve multi-core equal to increased processing power. Finally, it is a commonplace question. Because there is no sharding of data, Monad does not actually answer the requirements for nodes brought about by the expansion of the on-chain state. The following are its requirements for nodes, which have exceeded the limit that a home computer can bear. With the launch of its mainnet, if the data is not sharded, we may inevitably see Monad go the way of Solana. And the last and most important point is that optimistic execution is not suitable for parallelism in the blockchain field.
After mining for a while, Bob asked himself a question: "Why should I wait for Alice to come back before grinding? While she is grinding, I can load the car, because loading and grinding take exactly the same time, and we will definitely not encounter a state where we need to wait for grinding to be idle. Before Alice finishes mining, I will drive to continue mining, so that both of us can be 100% busy." This genius idea allowed them to return to twice the efficiency, and they didn't even need an additional mining car. Importantly, Bob redesigned the program, that is, the order in which threads execute, so that all threads will never be stuck waiting for shared resources within the core (such as mining cars and stone pickaxes).
This is the correct version of parallelism. By splitting the state of smart contracts, access to shared resources will neither cause a thread to enter the queue nor limit the speed of the final atomicity due to the data I/O pipeline.
The PREDA model exposes the access structure of the contract state to the execution layer at the time of contract code execution, so that the execution layer can easily and reasonably schedule and completely avoid the rollback of the execution result. This parallel mode is also called asynchronous parallelism.
Because only parallelism is asynchronous, adding threads will lead to linear improvement. Unlike the previous example, the capacity of the mining vehicle is upgraded but the mining vehicle runs empty due to backward mining equipment. PREDA's parallel execution environment is fundamentally different from Moand and Solana - just like the difference between multi-core CPUs and GPUs, the processing efficiency of its shared core will not be a bottleneck for parallelism, and there is no problem of data dependency during I/O reading and writing. More importantly, the parallelism of PREDA's parallel model will increase with the increase of threads, which is similar to GPU. In the logic of the blockchain, the increase of threads (VM) will reduce the hardware requirements of the full node, thereby improving performance while ensuring decentralization.
Finally, to reach the end of this parallel blockchain, the industry lacks not only architectural design, but also the semantic expression of parallel programming languages.
Just like Nvidia needs CUDA, parallel blockchains also need a new programming language: PREDA. Today's smart contract developers use parallel semantics to express, but cannot effectively utilize the support provided by the underlying multi-chain architecture (data sharding or execution sharding or both), and cannot achieve effective parallelization of general smart contract transactions. All systems use traditional common smart contract programming languages such as Solidity, Move, and Rust in terms of programming languages. These programming languages lack the ability to express parallel semantics, that is, they do not have the ability to express control flows and data flows between parallel units in parallel programming models and programming languages similar to CUDA in the field of high-performance computing or big data.
The lack of parallel programming models and programming languages suitable for smart contracts will result in the inability to complete the reconstruction of applications and algorithms from serial to parallel, resulting in the inability of applications and algorithms to adapt to the underlying blockchain system with parallel execution capabilities, thereby failing to improve the execution efficiency of applications and the overall throughput of blockchain systems.
This distributed programming model proposed by PREDA divides the contract state into fine-grained parts through programmatic contract scopes, and decomposes the transaction execution flow and distributes it on multiple parallel execution engines through functional relay semantics.
The model also defines the division scheme of contract state through programmable contract scope, allowing developers to optimize according to the access mode of the application. Through asynchronous functional relay, the transaction execution flow can be moved to the execution engine that needs to access the state to continue, realizing the movement of the execution process rather than the movement of data.
This model realizes the distributed division of contract state and the sharing of transaction traffic without developers having to care about the details of the underlying multi-chain system. Experimental results show that the PREDA model can achieve a throughput increase of up to 18 times on 256 execution engines, which is close to the theoretical parallel limit. The parallelism is further improved by using technologies such as partition counters and exchangeable instructions.
Blockchain systems traditionally use a single sequential execution engine (such as EVM) to process all transactions, which limits scalability. Multi-chain systems run parallel execution engines, but each engine processes all transactions of smart contracts, and scalability cannot be achieved at the contract level. This article discusses the essential core sharing of deterministic parallelism represented by Solana, and why optimistic parallelism represented by Monad cannot run stably in real blockchain application scenarios & The possibility of high-frequency rollbacks. And introduces PREDA's parallel execution engine. The PREDA team proposed a novel programming model to scale a single smart contract by dividing the state of the smart contract and distributing transaction traffic across execution engines. It introduces programmable contract scopes to define how the contract state is divided. Each scope runs on a dedicated execution engine. Asynchronous Functional Relay is used to decompose the transaction execution flow and move it across execution engines when the required state resides elsewhere.
This decouples transaction logic from contract state partitions, allowing inherent parallelism without data movement overhead. Its parallel model not only splits the state at the smart contract level, decouples the dependencies at the data publishing level, but also provides a Multi-Threaded execution engine cluster architecture similar to Move. More importantly, it innovatively launched a new programming model PREDA, which may be the last piece of the puzzle for blockchain parallelism.
Golden Finance launches the 2244th issue of the cryptocurrency and blockchain industry morning report "Golden Morning 8:00" to provide you with the latest and fastest digital currency and blockchain industry news.
JinseFinanceThe Particle Network People’s Launchpad goes live at 12 midnight UTC on February 5th and provides BTC holders and the ALLY community with an exclusive opportunity to participate in the Merlin Chain token distribution.
JinseFinanceOf the 27 Ethereum ETFs in the world, 20 are Ethereum spot ETFs and 7 are Ethereum futures ETFs. The top 10 global Ethereum ETFs all trade in Canada or Europe.
JinseFinanceLuxembourg, Saint Helena, Singapore, and Switzerland lead global interest in Bitcoin ETFs, ranking in the 90th percentile for search interest scores on Google Trends.
JinseFinanceDespite many prominent figures jumping on the Threads trend, many have not. From scammer accounts popping up to users not being able to delete their accounts, is Threads simply a rushed endeavour?
CatherineIs this another cage-fight-in-the-making? In an intriguing twist of events, Meta unveils its latest innovation — the Threads app — set to challenge Twitter's domain and after the latter’s recent woes.
CatherineThe impoverished country has launched an ambitious crypto project that includes using Bitcoin as legal tender, attracting investment and creating its own metaverse.
CointelegraphMore than double the number of people in developing countries think the Metaverse will affect their lives compared to developed countries, and they use it every day.
CointelegraphDeveloping countries have more than double the amount of people positive that the Metaverse will impact their lives and they'd use it daily in comparison to developed countries.
CointelegraphCanadian oil and gas miner Bengal Energy is set to begin its trial project of accessing formerly “stranded” gas wells with portable Bitcoin mining rigs.
Cointelegraph
