理解事务内存：《计算机架构合成讲座》推荐读物

4星 · 超过85%的资源需积分: 10 105 浏览量更新于2024-08-02 收藏 1.38MB PDF 举报

《事务内存合成讲座：计算机架构》是一本由Mark D. Hill编辑的专业书籍，收录在Synthesis Lectures on Computer Architecture系列中。该系列专注于探讨计算机设计、分析、选择和硬件组件连接的科学与艺术，旨在帮助读者实现计算机的功能性、性能和成本目标。本书特别聚焦于事务内存（Transactional Memory），这是现代并行编程中的一个重要概念，它允许程序员在并发环境中以一种直观的方式管理数据一致性，无需担心竞争条件和锁管理。事务内存由James R. Larus和Ravi Rajwar撰写，于2007年出版。事务是数据库管理系统中的一个概念，但在并发控制的编程模型中被引入，使得多个线程能够并发地访问共享数据，仿佛它们在一个单独的操作或事务中工作，而不会干扰对方。这种技术的关键在于提供了一种抽象，使得程序员可以声明一段代码为事务，系统内部会自动处理事务的原子性、隔离性和持久性，从而简化了并发编程的复杂性。书中深入剖析了事务内存的设计原理、实现方法和应用挑战，包括乐观锁、悲观锁、两阶段提交等策略，以及如何通过软件交易和硬件支持来提高性能。同时，它还讨论了事务内存与分布式系统、内存一致性模型、并行计算和量子计算等领域的交叉点，以展示其在计算机架构领域的广阔影响。《事务内存合成讲座》适合对并发编程、并行计算和硬件/软件协同感兴趣的专业人士，特别是那些寻求理解和实践高效并发控制方法的计算机架构师和程序员。它不仅提供了理论基础，还包含了一些实际案例和实验，使得读者能够将所学应用于实际项目中。此外，版权信息表明这本书由Morgan & Claypool出版，所有内容受版权保护，未经许可不得复制或传播。电子版和纸质版的ISBN号以及DOI都列出了便于查找和购买。对于希望深入研究事务内存并将其融入到计算机架构设计中的读者来说，这是一本不可或缺的学习资料。

P1: XXX

MOBK061-01 MOBK061-Larus.cls January 3, 2007 14:49

2 TRANSACTIONAL MEMORY

the number of instructions executed per second—without increasing clock speed. This means

that the performance of a well-formulated parallel program will also continue to improve at

roughly Moore’s law rate. Continued performance improvement permits a program’s developers

to increase its functionality by incorporating sophisticated, new features—the dynamic that has

driven the software industry for a long time.

Unfortunately, despite more than 40 years’ experience with parallel computers, few “well-

formulated” parallel programs exist. Programming parallel computers has proven to be far more

difﬁcult than programming sequential computers (which pose many difﬁcult challenges in pro-

ducing robust, reliable, and secure code). Parallel algorithms are more difﬁcult to formulate

and prove correct than sequential algorithms. A parallel program is far more difﬁcult to design,

write, and debug than an equivalent sequential program. The nondeterministic bugs that occur

in concurrent programs are notoriously difﬁcult to ﬁnd and remedy. Finally, to add insult to

injury, parallel programs often perform poorly. Part of these difﬁculties may be attributable

to the exotic nature of parallel programming, which was of interest to only a small commu-

nity, was not widely investigated or taught by academics, and was ignored by most software

vendors.

1.1.2 Difﬁculty of Parallel Programming

However, the authors believe that this explanation is insufﬁcient. Parallel programming is

fundamentally more difﬁcult than sequential programming. At its core, people have a great deal

of difﬁculty keeping track of concurrently occurring events. Psychologists call this phenomena

“attention” and have been studying it for a century. A seminal experiment was Cherry’s dichotic

listening task, in which a person was asked to repeat a message heard in one ear, while ignoring

a different message played to the other ear [3]. People are very good at ﬁltering the competing

message because they attend to a single channel at a time.

Concurrency and nondeterminacy greatly increase the number of items that a software

developer must keep in mind. Consequently, few people are able to systematically reason about a

parallel program’s behavior. Consider an example. Professor Maurice Herlihy of Brown Univer-

sity has observed that implementing a queue data structure is a simple programming assignment

in an introductory programming course. The parallel analogue, which allows concurrent en-

queues and dequeues, is a publishable result because of the difﬁculty of coordinating concurrent

access and handling the boundary conditions [4].

In addition, program analysis tools, which compensate for human failings by systemat-

ically identifying program defects, ﬁnd parallel code to be provably more difﬁcult to analyze

than sequential code. For example, context-sensitive analysis is a fundamental technique for

analyzing sequential programs. It improves the precision of analysis in defect-detection tools

and compilers by analyzing a function with respect to a speciﬁc calling context, instead of the

P1: XXX

MOBK061-01 MOBK061-Larus.cls January 3, 2007 14:49

INTRODUCTION 3

union of all possible call sites. In a concurrent program, combining context-sensitive analysis

with the synchronization analysis necessary to understand the communications between even

two threads results in an undecidable problem [5]. Fortunately, some analyses, such as safety

properties in threads that communicate only through mutual exclusion locks, are efﬁciently

decidable [6].

Finally—and a primary motivation for the strong interest in transactional memory—the

programming models, languages, and tools available to a parallel programmer have lagged far

behind those available for sequential programs. Consider the two prevalent parallel program-

ming models: data parallelism and task parallelism.

Data parallelism is an effective programming model that applies an operation simul-

taneously to an aggregate of individual items [7]. It is particularly appropriate for numeric

computations, which use numeric matrices as their primary data structure. Programs often

manipulate a matrix as an aggregate, for example, by adding it to another matrix. Scien-

tiﬁc programming languages, such as High Performance Fortran (HPF) [8], directly support

data parallel programming with a collection of operators on matrices and ways to combine

these operations. Parallelism is implicit and abundant in data parallel programs. A compiler

exploits the inherent concurrency of applying an operation to the elements of an aggregate

by partitioning the work among the available processors. This approach shifts the burden of

synchronization and load balancing from a programmer to a compiler and run-time system.

Unfortunately, data parallelism is not a universal programming model. It is natural and conve-

nient for some problems [7], but difﬁcult to apply to most data structures and programming

problems.

The other common programming model is task parallelism, which executes computa-

tions on concurrent threads that are coordinated with explicit synchronization such as locks,

semaphores, queues, etc. This unstructured programming model imposes no restrictions on the

code that each thread executes, when or how threads communicate, or how tasks are assigned

to threads. The model is a general one, capable of expressing all forms of parallel computation.

It, however, is very difﬁcult to program correctly. In many ways, the model is at the same (low)

level of abstraction as the underlying computer’s hardware; in fact, processors directly implement

many of the constructs used to write this type of program.

1.1.3 Parallel Programming Abstractions

A key shortcoming of task parallelism, however, is its lackof effective mechanisms for abstraction

and composition—computer science’s two fundamental tools for managing complexity. An

abstraction is a simpliﬁed view of an entity, which captures the features that are essential to

understand and manipulate it for a particular purpose. People use abstraction all the time. For

example, consider an observer “Jim” and a dog “Sally” barking from the backyard across the

P1: XXX

MOBK061-01 MOBK061-Larus.cls January 3, 2007 14:49

4 TRANSACTIONAL MEMORY

street. Sally is Jim’s abstraction of the dog interrupting his writing of this book. In considering

her barking, Jim need not remember that Sally is actually a one-year-old Golden Retriever

and certainly, Jim does not think of her as a quadruped mammal. The latter speciﬁcs are

true, but not germane to Jim’s irritation at the barking. Abstraction hides irrelevant detail and

complexity and allows humans (and computers) to focus on the aspects of a problem relevant to a

speciﬁc task.

Composition is the ability to put together two entities to form a larger, more complex

entity, which in turn is abstracted into a single, composite entity. Composition and abstraction

are closely related, since details of the underlying entities can be suppressed when manipu-

lating the composite product. Composition is also a common human activity. Consider an

engineered artifact such as a car, constructed from components such as an engine, brakes,

body, etc. For most purposes, the abstraction of a car subsumes these components and al-

lows us to think about a car without considering the details explored in automobile enthusiast

magazines.

Modern programming languages support powerful abstraction mechanisms, as well as rich

libraries of abstractions for sequential programming. Procedures offer a way to encapsulate and

nameasequence of operations. Abstract datatypeand objectsoffera way to encapsulateandname

data structures as well. Libraries, frameworks, and design patterns collect and organize reusable

abstractions that are the building blocks of software. Stepping up a level of abstraction, complex

software systems, such as operating systems, databases, or middleware, provide the powerful,

generally useful abstractions, such as virtual memory, ﬁle systems, or relational databases, used

by most software. These abstraction mechanisms and abstractions are fundamental to modern

software development, which increasingly builds and reuses software components, rather than

writing them from scratch.

Parallel programming lacks comparable abstraction mechanisms. Low-level parallel pro-

gramming models, such as threads and explicit synchronization, are unsuitable for constructing

abstractions because explicit synchronization is not composable. A program that uses an ab-

straction containing explicit synchronization must be aware of its details, to avoid causing races

or deadlocks.

Consider two examples fromTimHarris and Simon Peyton-Jonesof MicrosoftResearch,

a hash table that supports thread-safe

Insert and Delete operations. In a sequential program,

each of these operations can be an abstraction. One can fully specify their behavior without

reference to the hash table’s implementation. Now, suppose that in a parallel program, we want

to construct a new operation, call it

Move, which deletes an item from one hash table and insert

it into another table. The intermediate state, in which neither table contains the item, must

not be visible to other threads. Unless this requirement inﬂuences the implementation, there

is no way to compose

Insert and Delete operations to satisfy this requirement, since they

P1: XXX

MOBK061-01 MOBK061-Larus.cls January 3, 2007 14:49

INTRODUCTION 5

lock the table only for the duration of the individual operations. Fixing this problem requires

new methods such as

LockTable and UnlockTable, which break the hash-table abstraction

by exposing an implementation detail. Moreover, these methods are error prone. A client that

locks more than one table must be careful to lock them in a globally consistent order (and to

unlock them!), to prevent deadlock.

Thesame phenomenon holds forother forms ofparallel composition. Supposea procedure

p1 waits for one of two input queues to produce data, using an internal call to

WaitAny, and

suppose another procedure

p2 does the same thing on two different queues. We cannot apply

WaitAny to p1 and p2 to wait on any of the four queues, a fundamental loss of compositionality.

Instead, programmers use awkward programming techniques, such as collecting queues used

in lower level abstractions, performing a single top-level

WaitAny, and then dispatching back

to an appropriate handler. Again, two individually correct abstractions,

p1 and p2, cannot be

composed into a larger one; instead, they must be ripped apart and awkwardly merged, in direct

conﬂict with the goals of abstraction.

1.2 DATABASE SYSTEMS AND TRANSACTIONS

While parallelism has been a difﬁcult problem for general programming, database systems have

successfully exploited concurrency. Databases (DBs) achieve good performance on sequential

and parallel computers by executing many queries simultaneously and by running queries on

multiple processors when possible. Moreover, the database programming model ensures that

the author of an individual query need not worry about this concurrency. Many have wondered

if the programming model used by databases, with its relative simplicity and widespread success,

could also function as a more general, parallel programming model.

At the heart of the programming model for databases is a transaction. A transaction

speciﬁes a program semantics in which a computation executes as if it was the only computation

accessing the database. Other computations may execute simultaneously, but the model restricts

the allowable interactions among the transactions, so each produces results indistinguishable

from the situation in which the transactions run one after the other. As a consequence, a

programmer who writes code for a transaction lives in the simpler, more familiar sequential

programming world and only needs to reason about computations that start with the ﬁnal

results of other transactions. Transactions allow concurrent computations to access a common

database and still produce predictable, reproducible results.

Transactions are implemented by an underlying database system or transaction processing

monitor, both of which hide complex implementations behind a relatively simple interface [9–

11]. These systems contain many sophisticated algorithms, but a programmer only sees a simple

programming model that subsumes most aspects of concurrency and failure. Moreover, the

P1: XXX

MOBK061-01 MOBK061-Larus.cls January 3, 2007 14:49

6 TRANSACTIONAL MEMORY

abstract speciﬁcation of transaction behavior provides a great deal of implementation freedom

and allows the construction of efﬁcient database systems.

Transactions offer a proven abstraction mechanism in database systems for constructing

reusable parallel computations. A computation executed in a transaction need not expose the

data it accesses or the order in which these accesses occur. Composing transactions can be

as simple as executing subtransactions in the scope of a surrounding transaction. Moreover,

coordination mechanisms provide concise ways to constrain and order the execution of concur-

rent transactions.

The advent of multicore processors has renewed interest in an old idea, of incorporating

transactions into the programming model used to write parallel programs. While programming

language transactions bear some similarity to database transactions, the implementation and

execution environments differ greatly, as databases typically store data on disks and programs

store data in memory. This difference has given this new abstraction its name, Transactional

Memory (TM).

1.2.1 What Is a Transaction?

A transaction is a sequence of actions that appears indivisible and instantaneous to an out-

side observer. A database transaction has four speciﬁc attributes: failure atomicity, consistency,

isolation, and durability—collectively known as the ACID properties.

Atomicity requires that all constituent actions in a transaction complete successfully, or

that none of these actions appear to start executing. It is not acceptable for a constituent action

to fail and for the transaction to ﬁnish successfully. Nor is it acceptable for a failed action to

leave behind evidence that it executed. A transaction that completes successfully commits and

one that fails aborts. In this book, we will call this property failure atonicity, to distinguish it

from a more expansive notion of atomic execution, which encompasses elements of other ACID

properties.

The next property of a transaction is consistency. A transaction can modify the state of the

world, that is, data in a database or memory. These changes should leave this state consistent,

since subsequent transactions start executing from this modiﬁed state. Later transactions may

have no knowledge of which transactions executed earlier, so it is unrealistic to expect a transac-

tion to execute properly if an earlier transaction left the world in an arbitrary state. Transactions

start with the assumption that the world is consistent, and they are required to leave it in a

consistent state. The requirement is trivially satisﬁed if the transaction aborts, since it then does

not perturb the initially consistent state.

The meaning of consistency is entirely application dependent. It typically consists of

a collection of invariants on data structures. For example,

numCustomers contains the number

of items in the

Customer table or that the Customer table does not contain duplicate entries.

剩余225页未读，继续阅读

ecegatech

粉丝: 1
资源: 1

理解事务内存：《计算机架构合成讲座》推荐读物

Processor Microarchitecture An Implementation Perspective.pdf

Transactional Memory：并行编程的新范式

博途1200恒压供水程序，恒压供水，一拖三，PID控制，3台循环泵，软启动工作，带超压，缺水保护，西门子1200+KTP1000触摸屏

基于PLC的立体车库，升降横移立体车库设计，立体车库仿真，三层三列立体车库，基于s7-1200的升降横移式立体停车库的设计，基于西门子博图S7-1200plc与触摸屏HMI的3x3智能立体车库仿真控制

锂电池化成机 姆龙NJ NX程序，NJ501-1400，威伦通触摸屏，搭载GX-JC60分支器进行分布式总线控制，ID262.OD2663等输入输出IO模块ADA801模拟量模块 全自动锂电池化成分容

西门子Siemens PLC程序，博途V16 V17版，配方程序，RS485通讯控制变频器启停及速度控制，昆仑通态屏与1200通讯S7~1200为cPU为1214，屏采用为mgcS，程序案例

c3560c405-universalk9-mz.150-2.SE.bin

基于感知的H.264/AVC视频编码速率控制算法

共享打印机问题修复补丁

2024 DevOps 学习路线图

最新资源

锂电池化成机姆龙NJ NX程序，NJ501-1400，威伦通触摸屏，搭载GX-JC60分支器进行分布式总线控制，ID262.OD2663等输入输出IO模块ADA801模拟量模块全自动锂电池化成分容