OS:Concurrent and Distributed Software Design(4)

1.2 Supporting potentially concurrent applications

       有一些系统的并发处理是固有的，是必须的，而对于一些应用程序，并发处理的实现可以带来性能上的改善。这节继续讨论并发处理的需求。

The general motivation for exploiting potential concurrency in an application is that some or all of the following are the case:

l      There is a large amount of computing to be done

l      There is a large amount of data to be processed

l      There is a real-time requirement for the result

l      Hardware is available for running the potentially concurrent components in parallel.

1.2.1 Replicated code, partitioned data

/*感觉和SIMD有些像啊，只不过那是SIMD单指令流处理多数据，而这里是相同的代码处理不同的数据 -_-b

想起来老师讲过的关于并行处理的一个例子：

如果我需要一个文档的200份手抄版，那么我找200个人来做，时间等于200人中抄一份时间最长的人所用的时间(不考虑初始化、同步等问题)，这就是并行处理了，显然比一个人抄写快很多。但是如果这份文档在北京，我需要坐火车把它取回来，那么我坐火车取文档的活动是无法靠并行化来提高效率的。

现在回想起来，这个例子还是很经典的，顺便写在自己的读书笔记里：）*/

 

Replicated code, partitioned data的含义是这样的：有一个Manage of parallel computations来负责初始化计算与同步，然后以相同的“Copy of code”来处理数据，每一个Copy of code负责处理数据的一块。

大规模数据的搜索还是很适合这样的并行化的。

 

1.2.2 Pipelined processing

//流水线处理

       将代码分成不同的阶段，每个阶段对数据做固定的处理，数据依次流过每个阶段即可。比如编译器进行词法分析、语法检查、代码生成等工作，一旦第一块代码通过了词法分析，就可以进入下一阶段，而后面的代码会进入词法分析阶段。

       The requirements here are for the separate activities executing the various phases to be able to synchronize with each other: to wait for new data to become available or to wait for the next phase to finish processing its current data.

 

1.2.3 Tree-structured algorithms

       //树结构算法

       Many algorithms can be represented by a tree structure.

(1)   不同的子树可以进行并行化处理，而将结果交由更高的level。在这样的情况下，各个子树的处理是独立的。

(2)   也有一些应用是将要搜索的数据划分为树形结构。

(3)   其它情况，像语音识别，可能有需要将分支联合的情况。

树形结构的引入，比之于简单、静态、线性的数据分割，带来了更多潜在的并行化的可能，但是同时也带新的问题。

 

1.2.4 Shared data

       在一些应用中，数据是没有办法被分割处理的。而前面几节讲的算法都是在避免并发的访问相同的数据(partitioned data, Pipeline, Tree-structured algorithms)，即使如此，处理结果可能也要放入共享的数据结构中，或者处理完一块数据后可能请求处理别的数据块。

       其实，可以设计并发的算法来share数据的。Share读没有问题，改一个数据结构的不同的item也可以…但是…(we shall study this problem later)

 

1.2.5 Application areas

 

1.2.6 Requirements for supporting concurrent applications

Some requirements for the support of concurrency at the application level are:

l      To support separate activities

l      There is a need for these activities to be managed appropriately: to be created as required and stopped when no longer needed

l      There is a need for separate activities to synchronize with each other, and possibly to pass data when synchronized.

l      There may be a need for separate activities to share the data relating to the application; alternatively, the data may be strictly partitioned.