2014-05-26

SICP 1.2

SICP Lisp

1.2 手続きとその生成するプロセス

1.2.1

再帰的プロセス(recursive process)と反復的プロセス(iterative process)

手続きの定義の中で自分自身を再帰的に呼び出していく。

SICPで勉強を始めた時(=ソフトウェアの仕事を始めたばかりの頃)、最も関心したのがこの部分。
インタプリタが保持すべき情報量のオーダーがO(1)なのかO(n)なのか。
反復プロセスの場合、常に一定の記憶量でループを処理する事が可能。

C,Pascal等では反復的プロセスを行いたくとも、再帰呼び出しの際に
スタックを次々消費していくよう設計されている。
反復プロセスにはfor,while等の特殊なループ構造が必要。

また、Schemeの実装は末尾再帰的(固定記憶領域で再帰呼び出しが可能な性質)である事が
IEEE企画で定められている。

1.2.2

木構造を意識した再帰の実装。
与えられた題意から再帰的プロセスを導くのは比較的簡単(直感的に落とし込みやすい)だが、
反復的プロセスの実現は難しく感じる。

1.2.3

計算量(O(n))の話

1.2.4

再帰・反復用のコードの実装練習

q-1.16
反復的アルゴリズム設計のためのヒント

> 再帰時にその値が変化しない、不変量を定義すること

1.2.5 / 1.2.6

若干数学寄りの話なので略

まとめ

再帰的プロセス(recursive)と反復的プロセス(iterative)の違いが非常に重要。
自分自身を再帰的に呼び出す機能自体は同じだが、
インタプリタが計算終了までに記憶しておくべき記憶量に多大な差が生じる。

再帰回数が膨大になると(Cなどでは)スタックオーバーフローを起こす事になる。

2014-05-25

SICP 1.1

SICP Lisp

SICPの復習も兼ねて、学んだ内容を自分なりに噛み砕くため、
大枠と必要なら詳細をブログに書いてみる事にした。
不定期に。

1.1 プログラムの要素

1.1.1

schemeの演算規則など、基本的な文法説明。

1.1.2

defineと環境(大域環境の説明)

1.1.3

組み合わせ(式)を評価するためのインタプリタの基本的な手続きの説明
評価の規則は本質的に再帰的(rucursive)である。

> 部分式の評価結果に対し別な部分式が帰ってきた場合、再帰的に式を評価し続ける。
> 木構造と再帰の関係(tree accumulation)

特殊形式について

1.1.4

合成手続きの説明と実例。
defineについて再度説明。
defineによる手続きの定義は、すなわちその環境における手続きに対する名称の対応付けである。

1.1.5

置き換えモデルの説明。
3章で説明が出てくるが、set!等の破壊的代入が導入されるとこのモデルは破綻する。

作用的順序(applicative-order evaluation)と正規順序(normal-order evaluation)の違い。
実際にインタプリタが採用しているのは作用的順序(単純な展開ではなく、引数の評価と作用を行う)
schemeの式を眺めたとき、全ての部分式を展開するといった解釈方法は誤り。

1.1.6

condと特殊形式if
ifは何故特殊形式なのか？

> (if predicate consequent alternative)

のcons.とalt.は共に単一の式で無ければならない。

q1.5

> 正規順序によるインタプリタでは、処理が無限ループに入る。

1.1.7

小数・分数の扱い方の違い

1.1.8

手続きの定義の中に、自分自身の手続きの評価が含まれている。

> 再帰的な定義

ブラックボックスとしての手続き抽象
利用者に内部構造を隠す。

変数スコープとブロック構造の話

まとめ

1.1はschemeの言語としての部品と処理系に関する基本的な話。
以上、終わり。

2014-04-26

concurrency & parallel

CPU Architecture Linux

SICPを読んでいたら並列性(concurrently)が出てきたので、
coucurrencyとparallelの違いについて調べてみた。
日本語訳ではconcurrencyが並行でparallelが並列らしい。
SICPでの訳と逆だけど、まぁこれは日本語の問題なので略。

http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference

ここでの議論から引用。

coucurrency：２つ以上のプロセスが同一期間に実行可能状態(開始、実行、終了)にある事。
プロセスは必ずしも同じ瞬間(同時刻)に実行されていなくても良い。
　→シングルコア、マルチタスク(TSSによる時分割実行でも可)
parallel：２つ以上のプロセスが真に同時刻に実行される事。
　→マルチコア、マルチタスク

というニュアンスらしい。
概念的にはconcurrencyがparallelを内包している、という関係。
以上。

2014-03-31

openFrameworks + ofxBox2dでハマったのでメモ

openFrameworks

OFことopenFrameworksに興味が出たので、田所淳氏のサイトhttp://yoppa.org/で

公開している"Beyond Interaction"を参考に色々触っていたら、

addon(ofxBox2d)の導入でビルドエラーが出てつまづいた。

ググってみるとofxBox2dのサンプルビルドで躓いている人が多数なようなので、

簡易メモとして残す事に。

環境は64bit Ubuntu 12.04LTS & OF 0.7.4 (-> 0.8.1に入れ替え)

結論としては、openFrameworksとofxBox2dのバージョンが
合っていなかった事が原因。

* ofxBox2dの入手

git clone git://github.com/vanderlin/ofxBox2d.git

* README.md

Compatibilityの項より、使ってるOFのバージョンに合わせてcheckoutせよ、

と書いてあるものの、branchもtagも切っていない模様？

何故？？？

とりあえずこれをgit cloneし、OF 0.7.4で使用していたため、

Beyond Interactionに掲載のソースをビルドした際にコンパイル時にエラーが多発。

OF0.8.1に入れ替え、コードを数ヶ所書き換えたら動作しました。

* testApp.h (OF 0.8.1ではofApp.hにrename)

#ifndef _TEST_APP
#define _TEST_APP

#pragma once

#include "ofMain.h"
/* #include "ofxVectorMath.h" */
#include "ofxBox2d.h"

class testApp : public ofBaseApp{

public:
	void setup();
	void update();
	void draw();
	
	void keyPressed  (int key);
	void keyReleased(int key);
	void mouseMoved(int x, int y );
	void mouseDragged(int x, int y, int button);
	void mousePressed(int x, int y, int button);
	void mouseReleased(int x, int y, int button);
	void windowResized(int w, int h);
	void dragEvent(ofDragInfo dragInfo);
	void gotMessage(ofMessage msg);

	ofxBox2d box2d;
	/* vector <ofxBox2dCircle> circles; */
	vector <ofPtr<ofxBox2dCircle> > circles;
	
};

#endif

* testApp.cpp (OF 0.8.1ではofApp.cppにrename)

#include "ofApp.h"

//--------------------------------------------------------------
void ofApp::setup(){
	ofSetVerticalSync(true);
	ofBackground(0, 0, 0);
	
	box2d.init();
	box2d.setGravity(0, 5);
	box2d.createBounds(0, 0, ofGetWidth(), ofGetHeight());
	box2d.setFPS(30);
	
}

//--------------------------------------------------------------
void ofApp::update(){
	box2d.update();
}

//--------------------------------------------------------------
void ofApp::draw(){
	for (int i = 0; i < circles.size(); i++){
		circles[i].get()->draw();
		// circles[i].draw();
	}
	
	box2d.draw();

}

//--------------------------------------------------------------
void ofApp::keyPressed(int key){

}

//--------------------------------------------------------------
void ofApp::keyReleased(int key){

}

//--------------------------------------------------------------
void ofApp::mouseMoved(int x, int y ){

}

//--------------------------------------------------------------
void ofApp::mouseDragged(int x, int y, int button){

}

//--------------------------------------------------------------
void ofApp::mousePressed(int x, int y, int button){
	float r = ofRandom(10, 40);
	// ofxBox2dCircle circle;
	// circles.setPhysics(1.0, 0.8, 0.5);
	// circles.setup(box2d.getWorld(), mouseX, mouseY, r);
	ofPtr<ofxBox2dCircle> circle = ofPtr<ofxBox2dCircle>(new ofxBox2dCircle);
	circle.get()->setPhysics(1.0, 0.8, 0.5);
	circle.get()->setup(box2d.getWorld(), mouseX, mouseY, r);

	circles.push_back(circle);

}

//--------------------------------------------------------------
void ofApp::mouseReleased(int x, int y, int button){

}

//--------------------------------------------------------------
void ofApp::windowResized(int w, int h){

}

//--------------------------------------------------------------
void ofApp::gotMessage(ofMessage msg){

}

//--------------------------------------------------------------
void ofApp::dragEvent(ofDragInfo dragInfo){ 

}

上記のようにソースコードを変更後、makeを実行する事でビルドが成功。
以上、メモ書きまで。

2013-04-18

cache bounce

CPU Architecture

キャッシュバウンスなる物を始めて知ったのでメモ。

情報系の学生さんなら講義で学ぶのだろうか。

cache line bouncing

http://arighi.blogspot.jp/2008/12/cacheline-bouncing.html

・マルチプロセッサ環境(各プロセッサ毎にキャッシュ有)でマルチスレッドなプログラムを想定

・変数Ａ、変数ＢはそれぞれスレッドＡ，Ｂでのみ使用される

・スレッドＡはプロセッサＡで動作、スレッドＢはプロセッサＢで動作

という上記の条件において変数Ａ，Ｂが同一のキャッシュライン内に格納されてしまった場合、プロセッサＡ，Ｂ間のキャッシュコヒーレンスを保つためのプロトコル動作が大きなオーバーヘッドになり、結果としてパフォーマンスが低下する。

・・・という事らしい。

対策としてはキャッシュラインのサイズを考慮に入れて、適当なpadding用データを挿入する事で同一のキャッシュラインに格納される事を防いでいる模様。

こういった問題を体系的に学んでいない身としてはこういう問題は非常に面白い。

もっと技術情報収集のアンテナをもっと高くしたいなぁ。

2013-01-13

sshとVNCでマウスとキーボード削減

Linux Raspberry Pi

Raspberry Pi用に別途マウスとキーボードを接続するのが

面倒になったので、ホストPC(Debian Squeezeにて稼動中)からの

ssh＆VNCで一通りの作業が行えるよう設定を行った。

sshは初めから導入済みなので、まずはRaspberry Piにsshで接続。

$ssh pi@xxx.xxx.xxx.xxx(ラズベリーパイのIP)

VNCサーバーをインストール。

pi@raspberrypi ~ $sudo apt-get install tightvncserver

インストール後、初回時の起動でパスワード設定。

pi@raspberrypi ~ $ tightvncserver

とりあえずssh接続を終了。

pi@raspberrypi ~ $ logout

ホスト側にVNCクライアントをインストール。

$sudo apt-get install xvnc4viewer

$xvnc4viewer xxx.xxx.xxx.xxx(ラズベリーパイのIP):1

以上で接続完了。

今後はVNCとssh経由で触っていこう。

2013-01-13

とりあえずベンチマーク

Linux Raspberry Pi

Raspberry Pi関連でオーバークロックに関する記事を発見したので

何はともあれ追実験のベンチマークをしてみる。

http://www.raspberrypi.org/archives/2008

使用するツールはnbenchを使用。

http://www.tux.org/~mayer/linux/bmark.html

ソースコードを持ってきてRaspberry Pi上でネイティブコンパイル。

デフォルトの700MHzから始まり100MHzずつ動作周波数を上げていき、

nbenchによる計測を行った。

(オーバークロックの設定はsudo raspi-configから行える)

********overclock:none********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)

TEST                : Iterations/sec. : Old Index   : New Index
                    :                  : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT        :          206.72 :       5.30 :       1.74
STRING SORT         :          30.272 :      13.53 :       2.09
BITFIELD            :      7.8843e+07 :      13.52 :       2.82
FP EMULATION        :          41.029 :      19.69 :       4.54
FOURIER             :          2192.8 :       2.49 :       1.40
ASSIGNMENT          :          2.4705 :       9.40 :       2.44
IDEA                :          688.16 :      10.53 :       3.13
HUFFMAN             :          423.08 :      11.73 :       3.75
NEURAL NET          :          3.0546 :       4.91 :       2.06
LU DECOMPOSITION    :          76.329 :       3.95 :       2.86
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX       : 11.204
FLOATING-POINT INDEX: 3.644
Baseline (MSDOS*)   : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU                 :
L2 Cache            :
OS                  : Linux 3.2.27+
C compiler          : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc                : libc-2.13.so
MEMORY INDEX        : 2.434
INTEGER INDEX       : 3.102
FLOATING-POINT INDEX: 2.021
Baseline (LINUX)    : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.

********overclock:modest********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)

TEST                : Iterations/sec. : Old Index   : New Index
                    :                  : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT        :           235.4 :       6.04 :       1.98
STRING SORT         :          34.732 :      15.52 :       2.40
BITFIELD            :      9.0119e+07 :      15.46 :       3.23
FP EMULATION        :          46.984 :      22.54 :       5.20
FOURIER             :          2487.5 :       2.83 :       1.59
ASSIGNMENT          :          2.7195 :      10.35 :       2.68
IDEA                :          789.58 :      12.08 :       3.59
HUFFMAN             :          485.06 :      13.45 :       4.30
NEURAL NET          :          3.5198 :       5.65 :       2.38
LU DECOMPOSITION    :          84.286 :       4.37 :       3.15
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX       : 12.754
FLOATING-POINT INDEX: 4.118
Baseline (MSDOS*)   : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU                 :
L2 Cache            :
OS                  : Linux 3.2.27+
C compiler          : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc                : libc-2.13.so
MEMORY INDEX        : 2.751
INTEGER INDEX       : 3.550
FLOATING-POINT INDEX: 2.284
Baseline (LINUX)    : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.

********overclock:medium********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)

TEST                : Iterations/sec. : Old Index   : New Index
                    :                  : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT        :          262.56 :       6.73 :       2.21
STRING SORT         :          39.169 :      17.50 :       2.71
BITFIELD            :      1.0126e+08 :      17.37 :       3.63
FP EMULATION        :          52.676 :      25.28 :       5.83
FOURIER             :          2779.3 :       3.16 :       1.78
ASSIGNMENT          :          2.9656 :      11.28 :       2.93
IDEA                :          888.28 :      13.59 :       4.03
HUFFMAN             :          546.66 :      15.16 :       4.84
NEURAL NET          :           3.937 :       6.32 :       2.66
LU DECOMPOSITION    :           89.52 :       4.64 :       3.35
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX       : 14.266
FLOATING-POINT INDEX: 4.526
Baseline (MSDOS*)   : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU                 :
L2 Cache            :
OS                  : Linux 3.2.27+
C compiler          : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc                : libc-2.13.so
MEMORY INDEX        : 3.064
INTEGER INDEX       : 3.984
FLOATING-POINT INDEX: 2.510
Baseline (LINUX)    : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.

********overclock:turbo********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)

TEST                : Iterations/sec. : Old Index   : New Index
                    :                  : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT        :          308.88 :       7.92 :       2.60
STRING SORT         :           43.81 :      19.58 :       3.03
BITFIELD            :      1.1398e+08 :      19.55 :       4.08
FP EMULATION        :          59.592 :      28.60 :       6.60
FOURIER             :          3283.7 :       3.73 :       2.10
ASSIGNMENT          :          3.9185 :      14.91 :       3.87
IDEA                :          996.02 :      15.23 :       4.52
HUFFMAN             :          615.08 :      17.06 :       5.45
NEURAL NET          :          4.6261 :       7.43 :       3.13
LU DECOMPOSITION    :          122.22 :       6.33 :       4.57
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX       : 16.521
FLOATING-POINT INDEX: 5.601
Baseline (MSDOS*)   : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU                 :
L2 Cache            :
OS                  : Linux 3.2.27+
C compiler          : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc                : libc-2.13.so
MEMORY INDEX        : 3.631
INTEGER INDEX       : 4.535
FLOATING-POINT INDEX: 3.106
Baseline (LINUX)    : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.

クロック数が700MHzから1GHzまで上昇しているので、

最終的には概ね1.5倍程度の性能向上を達成している。

その内グラフィック関連のベンチマークもしてみたい。

あそびばLinux

Linux関連を中心に