sile

| 一章 Introduction - 導入

1.5 The Harsh Realities of Parallelization - 並列化の厳しい現実

• 理想化された世界で並列化について考えるのは楽しい
  • N倍多くのプロセッサが使えれば、N倍プログラムが早くなる！
• 現実にはそうはならない
• 例: 五人の友人が協力して家の壁を塗る話
  • 各々の作業スピードやそれぞれの部屋の広さが異なる場合、部屋数が5で割り切れない場合にどうなるか
• 並列化することで全体をどの程度効率化できるかといった分析は重要

---

sile

(in-package :actor)

(defparameter *current-process* (make-process :background nil))
(define-symbol-macro self *current-process*)

;; fork
(defun fork-impl (fn)
  (let ((proc (make-process)))
    (execute-fork-fn fn proc)   ; forkしたプロセスを実行する
    proc))

sile

(defpackage lock-free-queue
  (:use :common-lisp)
  (:export queue
           make
           enq 
           deq
           empty-p 
           element-count       
           to-list))
(in-package :lock-free-queue)

sile

The Relative Power of Primitive Synchronization Operations

• 新しいマルチプロセッサをデザインするとしたら、どんなアトミック命令を用意する？
  • いろんな論文に出てくるものを全て組み込むと複雑で非効率になる
    • メモリ読み書き、getAndDecrement()、swap()、getAndComplement()、compareAndSet()、その他諸々
  • 反対に、間違ったものを選択してしまうと最悪特定の同期問題を解決することが不可能になってしまう可能性がある
• 現実の問題を解決するのに必要な、同期操作プリミティブセットを特定するのがこの章の目的
  • そのためには各同期プリミティブのパワーを評価する仕組みが必要
  • 共有オブジェクト(キュー、スタック、ツリー、etc)を__wait-free__に実装できるかどうかを調べるのは、ひとつの方法
    • __deadlock-freedom__や__obstruction-freedom__といった性質は外部の環境(OS)に依存してしまうので不適切
• 各同期命令のパワーは等しくなく、明確な階層を形成している

sile

[5] Monitors and Blocking Synchronization

8.1 Introduction

• モニター
  • データと同期処理を結合する構造化された方法
  • オブジェクト指向言語のクラスに同期処理の管理を追加したようなもの
• なぜ有用か？
  • FIFOキューの例: モニターを使わないと次のような問題がある
    1. キューが満杯の場合に、空きができるまでenq()をブロックする、というような処理の実現が難しい

2. キューとロックの組み合わせを別々に管理する必要がある

sile

// CompositeLock::acquireQNode の実装

// メソッドを二つに分割:
//  1] ノードの所有権の獲得を試みるメソッド (acquireQNodeOwnerShip)
//  2] バックオフとかリトライ処理を管理するメソッド (acquireQNode)

private QNode acquireQNode(Backoff backoff, long startTime, long patience) {
    QNode node = waiting[random.nextInt(SIZE)];
    while(true) {

sile

//** 『The Art of Multiprocessor Programming』七章
//** A Hierarchical CLH Queue Lock **//
//
// HCLHLock::lock()の実装書き換え例
// (分かりやすさを重視しているため若干不正確な可能性がある)

public void lock() {
    QNode myNode = currNode.get();
    AtomicReference<QNode> localQueue = localQueues.get(ThreadId.getCluster());

sile

(deftype octet () '(unsigned-byte 8))

(defun read-le-uint (size in)
  (loop FOR i FROM 0 BELOW size
        SUM (ash (read-byte in) (* i 8))))

(defun read-bytes (size in)
  (let ((ary (make-array size :element-type 'octet)))
    (read-sequence ary in)
    ary))

sile

// sudo npm install -g http-proxy
// sudo npm install opts

var httpProxy = require('http-proxy'),
          url = require('url'),
          net = require('net'),
         http = require('http'),
         opts = require('opts'),
           fs = require('fs');

sile

[5] The Relative Power of Primitive Synchronization Operations

• マルチプロセッサプログラミングのために必要な同期命令プリミティブを考察する章
  • 同期命令 (or 同期オブジェクト)
    • アトミックレジスタ
    • FIFO Queue
    • multiple-assignment
    • common2 RMW (Read-Modify-Write)
    • compare-and-swap
• 諸々の同期命令はその consensus number によってレベル分けできる
• consensus number