借助多核处理器加速电子表格计算：面向非专业IT用户的并行编程方法

需积分: 10 85 浏览量更新于2024-07-16 收藏 1.3MB PDF 举报

"本文档是Alexander Asp Bock的博士论文，主要探讨了如何使非专业IT人员，即电子表格的终端用户，利用共享内存多核处理器加速电子表格计算。现有的解决方案往往需要用户参与或依赖计算集群，而该研究则致力于开发能够在完全透明的情况下自动加速电子表格重新计算的工具和算法，以适应现代计算机中的共享内存多核处理器。论文指出，由于电子表格的声明式和函数式特性，它们成为自动化加速的理想候选对象。" 这篇博士论文的核心知识点包括： 1. **电子表格的应用**：电子表格在科学、金融和工程等领域广泛应用，用于创建大型复杂的模型，这些模型对关键决策提供支持。由于其灵活性和易用性，它们深受领域专家的喜爱，但这些用户可能并不具备专业的IT技能。 2. **共享内存多核处理器**：随着技术的发展，共享内存多核处理器已经成为主流，为计算性能提供了显著提升。然而，如何让非专业IT背景的电子表格用户充分利用这种硬件资源进行计算加速是当前面临的一个挑战。 3. **用户交互与计算集群的限制**：目前的解决方案通常需要用户有一定的交互操作，或者依赖于计算集群来实现加速。这增加了用户的负担，并且限制了加速效果的普及。 4. **自动化加速的需求**：论文的研究目标在于开发无需用户干预的自动化工具和算法，使得电子表格的计算过程能在用户无感知的情况下自动加速，特别是在共享内存多核处理器的环境下。 5. **电子表格的声明式和函数式特性**：这是论文提出自动化加速策略的基础。声明式编程允许用户描述他们想要的结果，而不是如何达到结果，而函数式编程则强调计算的纯函数性和无副作用，这些特性使得电子表格特别适合自动化并行计算。 6. **并行编程方法**：论文探讨了如何将电子表格的计算任务转化为并行任务，以适应多核处理器的并行处理能力，从而提高计算效率。 7. **工具和算法的开发**：研究不仅限于理论分析，还涉及实际工具和算法的设计与实现，以解决实际问题，为电子表格用户带来更高效的工作体验。这篇博士论文对电子表格的并行计算进行了深入研究，对于提高非专业IT人员使用电子表格的效率具有重要的实践意义，同时也为未来的电子表格软件开发提供了理论指导和技术支持。

Chapter 1

Introduction

Spreadsheets continue to remain popular almost four decades after the

invention of Dan Bricklin and Bob Frankston’s VisiCalc [8]. Despite

their success and mainstream appeal they have also been criticised [9–

11] for their lack of the rigid programming doctrines expected by “real”

programmers. In a 1992 paper, aptly titled “Real Programmers Don’t Use

Spreadsheets”, Casimir writes:

“. . . therefore, I suggest that spreadsheets are intrinsically un-

interesting. . . The purpose of this paper is to list the few things

that should be known about spreadsheets and to warn would-

be researchers for the dullness of the subject.” ([10])

In a more recent paper from 2004, Wile writes:

“One must realize that spreadsheets are a success not because

they allow programming, but rather in spite of the fact that

they allow it!” ([11, p. 280])

Regardless, spreadsheets continue to remain popular tools for end-

user development today in areas such as ﬁnance and science for several

reasons in part being an amalgamation of a ﬁrst-order functional lan-

guage and a visual, data-driven tool. For example, users can modify

cells in the spreadsheet to get immediate visual feedback on the effects

of the modiﬁcation. Spreadsheets support convenient bulk operations

on cells such as summation and powerful copy-paste facilities. As a

functional language, they are typically side-effect free so users do in

general not have to worry about state. Scafﬁdi [12] estimated in 2017

2 Chapter 1. Introduction

that there would be 72 million professional spreadsheet users in that

same year. When viewed as functional languages [13, 14], that makes

spreadsheets one of the most widely used forms of functional program-

ming! This alone makes spreadsheets an interesting area of research

with the chance of new ideas beneﬁting millions of people.

The dichotomy of opinions on spreadsheets might stem partly from

the lack of academic involvement in their development [15]. Conse-

quently, spreadsheets have not been subject to the same rigorous princi-

ples enjoyed by “real” programmers of non-spreadsheet programming

languages. Interestingly, the research community’s seeming disinterest

in spreadsheets has been discussed at least as far back as 1985 by Mani

Chandy [15] in his invited address at the Principles of Distributed Com-

puting (PODC) conference.

“Software packages written using spreadsheets are now sold,

and in some cases, these packages display little concern for

the qualities espoused by academic computing sciences: cor-

rectness, simplicity, elegance, understandability and main-

tainability.” ([15])

The cumulative effect of these shortcomings likely contributes fur-

ther to the negative view of spreadsheets. Fortunately, the tide ap-

pears to have shifted since 1985 and there is now much more active

research on spreadsheets as we survey in chapter 3. In this thesis, we

follow suit and explore how different approaches to one such quality of com-

puter science, namely automatic or implicit parallelism, can be integrated

into the spreadsheet paradigm to accelerate spreadsheet computation. The au-

tomation is especially important as spreadsheet end-users are usually

non-programmers who have limited or no training in IT, but are domain

experts. Therefore, they should focus on problem solving not paralleli-

sation.

When on the subject of parallelism, one must inevitably mention that

the “free lunch is over” [16] as stated by Herb Sutter in a 2005 article on

the coming trends in concurrency and computer architecture. The gist

was that due to physical limitations in processor chips, we cannot sim-

ply buy a new, faster processor to accelerate sequential computation.

In response, hardware has instead evolved to utilise multiple shared-

memory processors to increase performance, leading to a recent rejuve-

nated age of parallel computing [17]. The present work is partly spurred

by this new age and today’s wide availability of shared-memory multi-

core systems in everything from personal laptops to mobile phones.

The idea of parallel spreadsheets is not new. In fact, Mani Chandy

also addressed this idea in his talk [15], suggesting a model for dis-

tributed spreadsheets wherein non-programmers could specify their prob-

lems, shielded from the details of the underlying implementation. The

spreadsheet could then be compiled to a distributed programming lan-

guage and executed on parallel hardware.

His suggestion and our work are both motivated by several attractive

properties of the spreadsheet languages that facilitate parallel execution.

We have already mentioned one of these properties: side-effect freedom

which means that multiple threads can in general operate on distinct

cells without having to worry about different execution interleavings

producing different results. Another property is cell immutability. The

formula language seldom provides ways in which to modify cells di-

rectly. Instead one must transform existing data so multiple threads do

not need to worry about concurrent modiﬁcations to a cell. Both side-

effect freedom and immutability originate in functional programming

languages and have long been heralded as some of the major strengths

of such languages [18, 19].

Spreadsheets are also declarative languages. End-users focus on

specifying what needs to be computed, letting the implementation care

about how it gets computed, as Mani Chandy also drew attention to [15].

Spreadsheets are also unique as functional languages in that they pro-

vide a grid of cells and an input-driven dataﬂow model of computation:

when a cell is modiﬁed, the new information automatically ﬂows for-

ward to cells that directly or transitively depend on the modiﬁed cell,

with immediate visual feedback. The dataﬂow system is constrained by

cell dependencies, another property of spreadsheets that makes them

attractive for parallelisation as independent cells can be evaluated in

parallel.

The attractive features of spreadsheets combined with their popular-

ity can serve as a medium for parallel computing to reach a wide audi-

ence of non-programmers [15]. This is the goal of the Popular Parallel

Programming (P3) project [20] which this dissertation is part of.

The need for parallel recalculation of spreadsheets may not be im-

mediately obvious but they are used to develop large, complex models

in ﬁnance and science. One example is a Monte Carlo simulation [21]

which took the authors 431 working hours to drastically improve the

1.1. Thesis Outline and Contributions 5

local, dynamic approach discussed in part I and a global, static approach

in part II. The work of Biermann et al. [22] has focused on a static, local

approach to automatic parallelism while the combination of global and

dynamic approaches remains unexplored in the context of spreadsheets.

We ﬁrmly believe that reading this dissertation will help convince

readers that spreadsheets are much more than a simple, dull modelling

tool which has intricate inner workings and design trade-offs that affect

everything from performance to end-user development. Contrary to the

quoted bleak words of Casimir [10], there are many exciting venues for

research to contribute to the future development of spreadsheets to the

beneﬁt of millions of users.

1.1 Thesis Outline and Contributions

The outline for the remainder of the thesis is as follows. In chapter 2,

we introduce some important concepts and terminology at the heart

of spreadsheets which will bring readers up to speed for the next two

chapters. Chapter 3 gives some overall background, speciﬁcally the con-

cept of dataﬂow, its history and how it relates to spreadsheets. This is

followed by a brief history of spreadsheets from their inception to con-

temporary systems and a survey of spreadsheet research. In chapter 4,

we describe Funcalc, the spreadsheet application used to implement our

work and how it differs from other spreadsheet applications.

The rest of the dissertation is split into three primary parts. The ﬁrst

two describe our different approaches to automatic parallelism given by

the two-dimensional spectrum in ﬁgure 1.1. The last part summarises

our ﬁndings and gives directions for future work.

Part I

In the ﬁrst major part of the thesis, we introduce our local, dynamic

parallel algorithms. In chapter 5, we ﬁrst discuss the changes neces-

sary to make Funcalc thread-safe, then present a task-based parallel cell

interpreter for spreadsheets along with a method for detecting cyclic

dependencies in parallel. A thorough investigation of the task-based

interpreter’s performance characteristics follows in chapter 6 and new

insights lead to an improved parallel interpreter in chapter 7. As an aca-

demic curiosity, we develop a different parallel cycle detection method

剩余229页未读，继续阅读

sinat_30114033

粉丝: 0
资源: 1

借助多核处理器加速电子表格计算：面向非专业IT用户的并行编程方法

PhD thesis

Bogdan_Iancu-OpenSIPS_Summit2015-OpenSIPS_2_1

Radu Bogdan Rusu's Phd Thesis（PCL在这篇论文中诞生）

PhD_Thesis.rar_PHD_iphone_thesis

Lavigne_Cyrille_ _201911_PhD_thesis.pdf

PhD_Thesis_GuoXu.pdf

PHD.Thesis.rar_PHD_witch

SUFE_SIME_Phd_Thesis_Defense_latex_Module_File.rar

phd_thesis

jameson_PHD_thesis

最新资源