Skip to content

Instantly share code, notes, and snippets.

@sile
sile / amp1-2.md
Created Jul 17, 2012
The Art of Multiprocessor Programming 読書会 第一回 一章後半~二章前半
View amp1-2.md

| 一章 Introduction - 導入

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

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

View actor.lisp
(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))
View lock-free-queue.lisp
(defpackage lock-free-queue
(:use :common-lisp)
(:export queue
make
enq
deq
empty-p
element-count
to-list))
(in-package :lock-free-queue)
@sile
sile / amp-3-5.md
Created Sep 1, 2012
The Art of Multiprocessor Programming 読書会 第三回 五章
View amp-3-5.md

The Relative Power of Primitive Synchronization Operations

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

[5] Monitors and Blocking Synchronization

8.1 Introduction

  • モニター
    • データと同期処理を結合する構造化された方法
    • オブジェクト指向言語のクラスに同期処理の管理を追加したようなもの
  • なぜ有用か?
    • FIFOキューの例: モニターを使わないと次のような問題がある
      1. キューが満杯の場合に、空きができるまでenq()をブロックする、というような処理の実現が難しい
      2. キューとロックの組み合わせを別々に管理する必要がある
@sile
sile / 1_acquireQNode.md
Last active Oct 11, 2015
Composit Lock
View 1_acquireQNode.md
// CompositeLock::acquireQNode の実装

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

private QNode acquireQNode(Backoff backoff, long startTime, long patience) {
    QNode node = waiting[random.nextInt(SIZE)];
    while(true) {
@sile
sile / HCLHLock_lock.md
Last active Feb 2, 2021
A Hierarchical CLH Queue Lock
View HCLHLock_lock.md
//** 『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());
View parse.lisp
(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
sile / proxy.js
Created Dec 17, 2012 — forked from anonymous/proxy.js
HTTP proxy server (node.js)
View proxy.js
// 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
sile / amp_5-6_summary.md
Last active Dec 10, 2015
The Art of Multiprocessor Programming 読書会 五章六章まとめ
View amp_5-6_summary.md

[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