2008-01-19

Am I satisfied with my English skills?

【Unit 19】
1. Are you satisfied with your English skills? Why or why not?
No, I’m not satisfied with my English skills. It’s because I can’t discuss in English fluently yet. Especially, I need a lot of time to make a sentence in English. So if I have a chance to discuss with people all over the world, I would be weaker brethren because of my English skills. In fact, when I took part in an Asian Business contest, I was not able to discuss with my members of my group.
Most of my team members are in famous University student: Beijing University, or Tsinghua University, or NUS and so on. They all would be excellent person who had outridden the competition, and I realized how low my actual power was. So to speak, this was my first experience to touch a global standard.
By good fortune, my team could win a third prize, so we could achieve result, but only me, couldn’t communicate other national people. I guess if I could talk and discuss with them in English in those day, I would get a lot of experience and make friends with them. In addition, if I had the knowledge of a specialist in those days, I would be able to exchange information and opinions of large talk with other national engineers.
So, I think I was not able to make good use of my opportunities. But, I’m sure another opportunity will come if I want. And then, I would like to make good use of my opportunities this time. Therefore, I’m not satisfied with my English skills.


2. Using the Language from Unit 19, discuss this statement: Money is more important than love.
I think money is as important as love, but according to then circumstances, money may be more important than Love, and Love may be more important than money.
It’s because I think money and Love both are important elements to spend your life with satisfaction. So if you are lacking in money, you couldn’t afford to take thought for anything else because of your circumstance, so then money is more important than Love.

And in another case, if you are overzealous in your quest for money, you will realize you’re not satisfied with your life because of lacking in something when you will be a senior.

Therefore, I think both of elements are very important, and the importance of those is often changed in your then stance. So, I think that to think about the argument is not smart very much. It’s because definitely, it is better for us to get both. So, if we have to think about it, all we should do is not thinking at which is important, but thinking at how we get both.

2008-01-17

Revolution solution

情報理論講義ノートは読み終わった。

結構つまんないわ。この教科。


【情報理論メモ@はじめだけ】
・一般的な情報とは
1.あることがらについてのしらせ。
2.判断や行動に必要な知識。

ex
[情報科学]
情報の性質・構造・論理を生成・伝達・変換・認識・利用などの観点から探求し、
情報機械の理論・応用を研究する学問

[情報理論]
情報の量を定義し、情報の変換・伝送を体系化した数学的基礎理論。
通信・物理学的測定・コンピューター・生物学などに影響を与えた。
シャノンによって創始。

・シャノンの考えた"情報"
不確実なものをどのくらいかくじつにしてくれるか。

・情報の性質
ありがちなことや予想されることはあまり価値がない
予想だにしない意外なことは情報として価値が高い。
cf.ニュースバリュー

→情報の価値は、受け手を取り巻く環境によって異なる。



【ARPA-NETの人の講義】
新世代のインターネットの講義聴いてきました。

でも、ちょっと微妙…

正直ITの歴史とか大体知ってるから、これからの話だけに絞って話してくれた方が

面白かった気が。。。

あとカタコトの日本語でプレゼンなら、いっそのこと英語の方がよかったような。。。

まぁいいか。

Asia FI school(www Asia FI net)
2008 2 18-22 seul, Mobile/Wireless
2008 8 Architecture
2009 1 China in Japan, Mobile/Wireless

Main Technology/(Made in)/Age

↓Vint Cerf
TCP/IP (USA)/20s
WWW (EUROPE)/30s
Blowser (USA)/20s
Search (USA)/20s
WiFi (USA)/30s
Client/Server (USA/EU)/20s
Wiki? (USA)/20~30s
Ethernet (USA)/20s
P2P (USA)/10s
Router (USA)/20~30s
-------
Internet Engineering(USA)/20~30s


Quwstion:
1969:パケットスイッチに成功した。
当時のSpped:50b(Telegraph)
現在:56kbps

1970s


cosmos.kaist.ac.kr
cs744

Q&A:
Licklidar
Dream Machine

Sutherland

2008-01-16

Notation

あ~、思ったより教科書が頭に入ってないことにショックorz

とりあえず、帰ったら言語論のpdfを一から読み直そう。

課題に関しては、一応ここまでにしておいて、
あとは期末試験後に回そう。



最近、dragon ashの古いアルバム(Viva la Revolutionとか)にまた嵌まってしまった。


[必要な作業@memo]
【全般】
PDFの熟読

【関数toTokens】
・ノードが初期ノードかどうかを調べる関数or方法
・ノードを単純なstring型にする関数or方法

・トークン数列に文字列を加える方法
・トークン数列の文頭に付加する関数or方法
・トークン数列の末尾に付加する関数or方法

・ノードを演算子ノードかどうかを調べる関数or方法
・演算子ノードの最初の子を見つける方法or関数
・演算時ノードの残りの子ノード達を探す方法or関数

・開き丸括弧が必要とされているかどうかを見極める方法or関数(←多分ない)
・閉じ括弧が必要とされているかどうかを調べる方法or関数(←コレは多分無い)

【関数isParenthesisRequired】
・丸括弧が必要とされているかどうかを調べる方法or関数
・演算子の優先度と結合性を調べる関数
・↑の結果を比較する関数orアルゴリズム



[メソッド一覧]
・Infix.java :中置記法
protected void parse(final String[] tokens) throws InvalidExpressionException {
計算式であるトークンの数列を構文解析する。
加算とか減算とか平均の演算子と、乗算とか除算とかmodの演算子を解析する。
限りなくメインメソッドに近い。
* 引数tokensは計算式をトークン化した表現


private String[] getSubExpression(final String[] tokens, final int indexStart) {
* 丸括弧の中にあるトークンのサブ数列を取り戻す。
* 引数tokensとは、計算式のトークンの数列である。
* 引数indexStartとは丸括弧を探し始めるindexのことである。
* 丸括弧の中にあるトークンのサブ数列を返す。


private void setChildNodeAtFreeBranch(IOperatorNode nodeOp, INode node) throws InvalidExpressionException {
* どのノードも存在していない位置にある演算子ノードの子ノードとして、設置する。
* 引数nodeOpとは、演算子ノードのこと。
* 引数nodeとは、演算子ノードの子ノードになるはずのノードのこと。


private boolean isFilledOperator(final IOperatorNode nodeOp) {
* 演算子ノードが全ての子ノードを持っているかどうかを返す(まだ設置できるかどうかを確かめるため?)
* nodeOpとは、演算子ノードのことである。
* もしも、その演算子ノードが全ての子ノードを持っていたら、trueを返す。そうでなければ、falseを返す。


protected Collection toTokens(INode node) {
* 計算式の抽象構文ツリーからのトークンの訂正を返す。
* 引数nodeは計算式の抽象構文木の根ノードのことである。
* 計算式のトークンの訂正を返す。


//↓ココが必修訂正箇所
private Collection toTokens(INode node, IOperatorNode opParentNode) {
* 計算式の抽象構文木からトークンの訂正値を返す。
* 引数nodeは計算式の抽象構文木の根ノードを返す
* 引数opParentNodeとは、根ノードの親ノードとなる、演算子ノードのことである。
* 計算式のトークンの訂正値を返す。

// もし、そのノードが初期ノードだったら
// そのノードを単純にstring型にして、トークンの数列に文字列を加える。
// もし、そのノードが演算子ノードだったら、
// もし、開き丸括弧が必要とされていたら、開き丸括弧を最初のトークンの数列に追加して、
// 演算子ノードの最初の子を、トークンの数列に加えて、
// その後、演算子記号を、トークンの数列に追加して、
// そして、演算子ノードの子ノード達の残りを、トークンの文字列に加える。
// もし、閉じ括弧が必要とされていたら、トークンの末尾に閉じ括弧を加える。


//↓ココが必修訂正箇所
private boolean isParenthesisRequired(final IOperatorNode opCur, final IOperatorNode opChild) {
* 丸括弧が必要とされているかどうかを返す。
* 演算子の優先度と結合性を元にして、
* 演算子ノードとその子演算子ノードを比較して、
* 引数opCurとは、現在フォーカスされている演算子ノードのこと。
* 引数opChildとは、現在の演算子ノードの子ノードである、演算子ノードのこと。
* もし、子ノードのために丸括弧が必要とされていたらtrueを返す。そうでなければfalseを返す。


private boolean hasHigherPrecedenceThan(final IOperatorNode opNodeA, final IOperatorNode opNodeB) {
* 演算子が他の演算子より優位かどうかを返す
* 引数opNodeAは、現在フォーカスされている演算子ノードのこと。
* 引数opNodeBとは、現在の演算子ノードと比較する演算子ノードのこと。
* もし現在の演算子ノードがもう一方の演算子ノードより
高い優先度をもっていたらtrueを返す。そうでなければfalseを返す。


private boolean equalsPrecedence(final IOperatorNode opNodeA, final IOperatorNode opNodeB) {
* 演算子がもう一方の演算子と同じ優先度を持っているかどうかを返す。
* 引数opNodeAとは、現在フォーカスされている演算子ノードのこと
* 引数opNodeBとは、現在の演算子ノードと比較する演算子ノードのこと
* もし現在の演算子ノードがもう一方の演算子ノードと
同じ優先度をもっていたらtrueを返す。そうでなければfalseを返す。


private int getPrecedence(final IOperatorNode opNode) {
* 演算子の優先度を返す。
* 低い値は優先度が高いことを意味する。
* マイナスの値はエラーを返す。
* 引数opNodeとは、現在フォーカスされている演算子ノード。
* 演算子の優先度をint型の数値で返す(-1,0,1)多分?


private int getPrecedence(final int opID) {
* 演算子の優先度を返す。
* 低い値は優先度が高いことを意味する。
* マイナスの値はエラーを返す。
* 引数opNodeとは、現在フォーカスされている演算子ノード。
* 演算子の優先度をint型の数値で返す


private int getAssociativity(final IOperatorNode opNode) {
* 演算子の結合性を返す
* 負の値はエラーを表示する。
* 引数opNodeとは、現在フォーカスされている演算子ノード。
* int型の数値として、演算子の結合性を返す。


private int getAssociativity(final int precedence) {
* 演算子の結合性を返す。
* マイナスの値はエラーを表示させる。
* 引数opNodeとは、現在フォーカスされている演算子ノード。
* int型の数値として、演算子の結合性を返す。


public String getNotation() {
* 計算式のための表記法を返す。


protected boolean isSpaceSeparatorNeeded() {
* もし空白文字が、stringの表現をセパレータとして必要とする場合
* 計算式の表記法に向けたトークンの数列から生成された
* もしも空白文字が必要とされたらTRUEを返す、そうでなければFALSEを返す。


・IOperatorNode.java:演算子ノードのインターフェース

* 文字列として演算子記号を返す。
public String getOperator();

* 演算子の識別子(演算子ID)を返す
public int getOperatorID();

* 演算子のアリティを返す。
public int getArity();


・OperatorNode.java
private static int operatorString2operatorIndex(final String strOp) {

private static String operatorIndex2operatorString(final int index) {

/* package */
static boolean isOperator(final String strOp) {

private static int operatorID2operatorIndex(final int id) {

private static int operatorIndex2operatorID(final int index) {

private static int operatorString2operatorID(final String strOp) {

private static String operatorID2operatorString(final int id) {

private static int getArity(final int id) {

-Constructor-
protected OperatorNode(final int id) {

protected OperatorNode(final String strOp) {

-method-
*演算子のstring表現を返す
public String getOperator() {

*演算子の識別子を返す
public int getOperatorID() {

*子ノード達の数を返す
public int getNumberOfChildren() {


* indexの位置にある子ノードを返す。
* 引数indexとは、子ノードのindexのこと。
* indexの位置になる子ノードを返す。
public INode getChildNode(final int index) {


* indexの位置にある子ノードとして、そのノードをセットする。
* 引数indexとは、子ノードのindexのこと。
* 引数childNodeとは、indexの位置にセットされるノードのこと。
public void setChildNode(final int index, final INode childNode) {


* 子ノードのindexを返す。
* 引数nodeとは、子ノードとしてチェックされるノードのこと。
* もし、そのノードが子ノードであれば、indexの値を返す。そうでなければfalse(NOT_FOUND)を返す。
public int getChildIndex(final INode node) {


* このノードのコピーを作る。
* 引数bDeepとは、もしもtrueならば、deepcopyをつくり、
そうでなければshallowcopyを作る。
public INode cloneNode(final boolean bDeep) {


* このオブジェクトのコピーを生成する。
* コピーされたオブジェクトを返す。
protected Object clone() {


* ノードを評価して、評価した結果を返す。
public int evaluate() throws EvaluationException,InvalidVariableException {


* ノードを評価して、評価した結果を、環境と共に返す。
* 引数envとは、環境のこと
* 評価した結果をint型の数値で返す。
public int evaluate(final Environment env) throws EvaluationException,InvalidVariableException {


* このノードのストリング型の表現を返す。
public String toString() {




[演算子識別子]
0=no operator
1=addition
2=subtraction
3=multiplication
4=division




precedence
優先、優位

denote
~を意味する、示す、~を表示する、~の名称である

operator
演算子

arithmetical
演算の、算数の

arithmetic expression
計算式
r
associativity
結合性

identifier
識別子、一意名

sequence
数列、列

representation
表示、表現、説明

modulo
剰余演算子modのこと

token
しるし、証拠、表象
<コ>トークン信号、、優先権信号

recursively
再帰的に

whitespace
空白スペース

parse
構文解析をする

partial
部分的な、一部の

notation
表記法


[Arity]
アリティ (arity) とは、
関数や演算子に対し、それらが取る引数 (オペランド) の
個数を意味するのに、代数学、論理学、計算機科学などにおいて
用いられる用語である。

項数のような訳語が当てられる場合もあるが、
arity と英単語のまま用いられることも多い。

この用語は、ラテン語起源の英単語において単項の演算を
unary (operation), 2 項を binary, 3 項を ternary,
さらには一般に n 項を n-ary というように
接尾辞 -ary をつけた形容詞で引数の個数を表すことから来ている。


[Shallow copy]
オブジェクトをコピーする際に、
参照先をそのままにして、
そのオブジェクト自体だけをコピーすること。

反対に、
そのオブジェクトが参照しているオブジェクトまでコピーして、
参照 (ポインタ) を書き換えることを deep copy と言う。


[Deep copy]
オブジェクトをコピーする際に、
そのオブジェクトが参照しているオブジェクトまでコピーして、
参照 (ポインタ) を書き換えること。

反対に、
参照先をそのままにして対象オブジェクトのみを
コピーすることを shallow copy と言う。

Have I improved my English speaking skill for this late stage?

フーリエ発展課題終わったぁぁぁぁ~。
アドバイスをくれた友達sにはとても感謝。サンクス!

あとはプログラミング言語論の課題だけだ。

ただこの課題は期限が目一杯取ってあって、
ある程度アドバンテージを取っておけば
期末試験後からでも着手できるっぽいから、
これは最後のお楽しみということで、試験後に回そう。


しかし、フーリエの個別課題のOPアンプ数は1~3個で、
Low Pass FilterとかHigh Pass Filterとかが何もかかっていない
タダの正弦波or方形波の個別課題もあるのに 、 自分に与えられた
個別課題の回路が∫x(1)tdt-∫x(2)tdt だったのはちょっと不運だったな。
OPアンプMAXじゃないッスかww

でもおかげで積分回路も減算回路もそれなりに理解できた、と思いたい。
電子回路もこの調子で理解していきたいな。



そういえば、
明日はARPA-NETの開発に携わった唯一のアジア人がウチの大学に来るそうな。
タイトルは新世代のインターネット、だったっけかな。
試験も近いけど、こんな機会はあんまりないんで、是非とも聞いておきたい。


追記:
プログラミング言語論の最終課題はヤバイ。。。
ただでさえソースコードが腐るほどあるのに、
一つのソースコード理解するだけでも、昇天しそうだった。
流石、IBMな人は求める水準も違うぜw。


【Unit 17】
1. Have your speaking skills improved since you started Tutorial English? Why or why not?
I would assume so. Especially, I think I have been able to make a sentence, speaking the sentence partway. I think it means I have a little better understanding of the way to make a sentence.
I guess there are two points why I have been able to do that.

One point is that I read the book called “Feeling English grammar by your heart”. This book is completely different from traditional reference book at grammar. This book is not based on traditional principles in Japan about English grammar, for example “KATEI-HOU”, “HUKU-SHI TEKI YOHO”, “KAKO-BUNSHI” and so on. It means the authors of this book focus on the thinking and feeling of the native speakers of English in speaking. So reader learns the thinking and feeling to be closer to the native speakers. So I have learned my thinking and feeling to speak English through the book.

Another point is that I could put into practice what I have learned above through attending Tutorial English. I think I would not have improved my speaking skills that far if I just learned the thinking and feeling through the book. But I had much chance to put into practice what I have learned in Tutorial English. So I could not only learn the method but also put into practice the method. Therefore, I have improved my speaking skills through the book and Tutorial English.

So I’m really grateful to the authors of the book and Tutorial English, and I would like to keep improving English skills up.


2. Using the Language from Unit 17, tell me about a fun trip you went on. (What did you do? How was it?)
I went on Beijing in China one year ago. It was amazing experience, and I made up my mind never to go Beijing except errand which I have to go there. I went on Beijing to participate in a convention, and I think I got very wonderful experience through this convention and its program. But I think the place is not good.

For example, when I drank orange juice for breakfast in accommodation, the water is not orange juice. Correctly, that’s true it might be orange juice, but it tasted too plain. It’s closer to water coloring orange than orange juice. Incidentally, foods prepared as breakfast are cold.

And another example, I got out to a flea market after convention, and I shopped around there. The market had bizarre articles for sale. Especially at food, the articles were very bizarre. It’s because some of foods are insects. I know some of insects are esculent because in Japan we can eat some insects at restaurant and buy edible insects as food like a locust and larvae of bee and so on.

But, I have never heard that we can eat a cockroach and we can eat a locust with its feet. I’m sure these insects are not fully guaranteed that to eat them is good for health. But unfortunately, someone who is member of convention is interested in them, and he suggested that take a stone-scissors-paper and a person who lose this game have to go through a penalty game which eats insects.
Resultingly, I lost that game, and I have to eat it. A little fortunately, I don’t have to eat cockroach.
And I ate a would-be edible insect. I would never forget that green-hued liquid was released from inside it when I chew it.

Well…as a consequence, it might be good experience because I learned an importance of food culture through that event.


【Unit 18】
1. Is learning English fun for you? Why or why not?

Learning English is very fun for me. But just to learn English is not fun. I think it is fun for me to be able to do something as my English skill improves. For example, if I want to know or to use some new technical information, I would search on the web, but it is difficult to search new technical information only Japanese, so it would need to search in English and need ability to read English sentence. At the same time, if I can’t understand new technical information, I must ask a question, using a bulletin board system.

So if I touch a something of frontier, it can’t be avoided. But conversely, if I have high English skill, I can get much chance to touch a something of frontier, and I also touch a culture of diverse country.

Therefore, it is not fun for me just to study English, but ahead of the hard study, I think I will be able to get much chance than now.


2. Using the Language from Unit 18, disagree with the following suggestion and then make your own suggestion: Let's go to Lotteria for breakfast!

May be, but I would rather not go to such a restaurant for breakfast. It’s because I’m very keen to lose my weight, so if you would not mind taking a low-calorie breakfast, I would like to go to a café. If you are OK with that, I would guide you to my favorite café.

2008-01-15

CPUにおける仮想アドレスと物理アドレスについて

MAP=関数。
「V→P U 空集合」の順番にアクセスする
V=仮想アドレス
P=物理アドレス
U=ユニオン

[たとえ話]]
起き上がって仕事をしようとしても、今まで休んでいたから、
以前使っていたメモリ使用領域はDiskに追い出されていることがある


[想定されるケース]
MAPで物理アドレスが求まる場合と
物理的なメモリには無くてDiskに追い出されている場合(→空集合へいくケース)がある。

//深い話については3年次のOSの授業でやる。
!!表は試験に出ないけど、表の理解はとても大事!!

[Pageについて]
今の多くのコンピュータは4kB(4096=12bit)単位でメモリ領域間を移動する。
1pageが標準。
2^10≒1,000
2^20≒1,000,000
ページは読み書きしたいアドレスが属する番号を示している。


[仮想アドレス]
仮想アドレスのうち
上位20bitは残る→PPNへ
上位20bitを使って、メインメモリの中にキャッシュされているページテーブルの場所を示して、
ページテーブルのエントリーを見に行く。
※ページテーブルは必ずどこかにある!


[validの役割]
validが立っている(valid=1)と、
validが立っていない(valid=0)場合がある
→ページフォールトになるととても時間がかかる。

virtualアドレスをコンピュータの中のアドレスに変換する(=phisicalアドレスを作る)。


[仮想アドレス下位]
下位12bitは上位20bitで得たアドレスを読み書きするのに使用する。


[単語説明]
MMU=Memory Management Unit :メモリを管理するユニット
VA=Virtual Address :仮想アドレス
PTEA=Page Table Entry Address :情報のありかを示す場所。(一種の索引で「どこを見るか」ということ)
PTE= Page Table Entry :情報の中身?
PA=Physical Address:物理アドレス


[MMUの動作]
一般的に一往復多い(②と③の部分)→もったいない。
最近のプロセッサーはそこを頑張ってなんとかしようとしている cf."TLB"
キャッシュに当たったとしても②と③はもったいない。


[悲惨場合]
1. ②でMMUにない場合
2. ④Exceptionで"Page faultだった"という報告をする。
→その後の作業はOSに任せる
3. victim pageをDiskに追い出しnew pageをキャッシュに置く。
→この動作もまた、とても時間がかかる

(補足)
ページテーブルのアドレスがあればMMUに帰ってくる。
PAもキャッシュにあればProcessorを介してMMUに戻る。
無ければL2やMemoryにアクセスしていく。


[往復問題]
L1にあったとしても、L1キャッシュが込んでくると、
他のメモリ参照のせいで、キャッシュしたのが追い出されてしまう。
また、読み出すのに少なくとも1サイクルの遅れがある。

・MMUの中にキャッシュがあればよいのではないか?
→(HOTな話題)TLB = Translation Lookaside Buffer
small hardware cache in MMU

ハードウェアでそもそもメモリを扱おうとするプロジェクト?
ページテーブルは大きい。1Pは4kだから運十万ぐらいにいく。
だからそのうちの、とってもよく使う部分だけをMMUに入れてしまおうという内容。

[第2ラウンドの話]
TLB hit
TLBに物理アドレスと論理アドレスの関係の表がキャッシュされていたら、
VPN(= Virtual Page Number)で聞き、PTEで返してもらう。
結果:1サイクル得する。

不幸にもTLBにキャッシュされていなかったら、キャッシュメモリに行って2往復する。

なるべくメモリをうまく使えるプログラムを作って、VAの無いようにする。

実際にはTLB MissはあまりMissらない。
→何故?→教科書参照


[64bitと32bitについて]
1Pは4kB単位
最近の64bit(athronとか)は、全部のbitを使うわけではない。

PTEが4バイトで済む→物理メモリの何テーブル目かが分かる。
64bitマシーンはhardwareサポートしている。256GBある?→ただし効率が悪い。
→表というのは大きくなりすぎると、検索するのが大変。
→索引を幾つかに分ける。索引のための索引を作る。cf.Level1 table ⇔ Lebel2 tables
たくさんある索引のうちのどの索引にあるか調べる。
→2 Lebel Tables、一般的なpentiumでは大体用いられている。

256GBの使ってないものを置く必要性をなくしている?


[Case study]
-Pentium系のマシンはどうなっているのか?-

INTEL P6
core2とかpentiumとかその辺のマシンについて
Pentium →93年に出来た。 cf.教科書参照15-213, F'06
2~3年前はPentium4

ただし、pentium4はpentium3にはない問題が浮上した
→発熱が大きい

INTELもここら辺で気付いた。
・4GHzを出そうというプロジェクトを辞めて、Pentium3に戻り、拡張してCore2duoを作った。
→熱の問題に対処した。
dual core→一個のCPUにたくさんのプロセッサを乗っけること。

だから、Pentium4を勉強する必要はあまり無い。

※技術が進歩しているので教科書の具体値は微妙に違う。

[P6 Memory System][
この図はそれほど勉強する必要は無い。


[Review of Addreviations] 略語集

[Overview of P6 Address Translation]
これが理解できたら大丈夫。

CPUは左上にある。
一周するのには、様々なルートがある。→様々なサイクル数が考えられる。
Virtual Addressは上と下で20bit=VPN, 12bit=VPOに分かれている。
VPOはPhysical Addressを読み書きする。=PPO
PPNとPPOでキャッシュを見に行く。
CO=Cache offset (5bit)
L1は一個ずつの箱が32bit?
全部で512個
cf.車両。店員512名。隣の列車には移れない。

CI = Cache Index :索引
CT = Cache Tag :聞きに行くためのタグ

見つからなかったら、残念ですね。ということでL2 and DRAMに行く。
→とても遅くなります。


[VAの上位20bitの部分について]
ページテーブルはどういう風になっているのか。
1ページ=12bit
あまり利用されないPage Tableは遠いところに追い出される。

PDBR=Page Directly Base Register


[今日のスライド9P]
さっきの絵の左下の拡大図
20bitをさらに10bit/10bitに分けて、
VPN1でLevel 1を、VPN2でLevel2 Tablesを示す。
レベル1のエントリ…この部分はあまり理解しなくても良い。
//省略


[大事なところ=一番うまくいくケースについて考える]
VPNがPPNを効率的に引ける場合。
TLBはキャッシュと大体同じ構成をしている。
本当に書いているかどうかはTLBTと一致しているかどうかで調べる。
店員は64ページ。TLBはほぼ確実に当たってほしい。


[製作者の意図する理想]
64P×4kB=256kBぐらいのメモリアドレス空間はとても早く実行してあげましょう
それ以外は遅くなってしまうでしょう。

TLBIで何号車にいるかを調べる。
TLBTで比較。

コレがうまくいくと、あとはキャッシュにいく。

アドレスを計算するためのキャッシュ=TLB
データを計算するためのキャッシュ=L1,L2,Memory and so on

VPNの仮想番地から物理番地を求めるにはある程度の手間がかかる。
キャッシュを求めるためには、またある程度の手間がかかる。

キャッシュの切れ目に注目すると、
→一致している!
→VPOはPPOと変わらないので、VPIがごちゃごちゃやっている間にキャッシュの表を引く作業を実行している。


[CPUの見方]
キャッシュがどれだけ乗っていたか。
テストプログラムからassociabiltyを見ている。

例、先生のCPU
L1は32kB
L1 8way
Line size 64kB

一個64biteが8個並ぶ。←キャッシュセット
512kB/setが縦に64set並んでいる。


[TLBの話]
L1 D-TLB
Entries 128
Associavilty 4-way
□□□□
↑Entry

コレが
□□□□
□□□□

□□□□
↑32setsある。


[何故ストライドアクセスでスパイクが起こるのか?]
//Page2参照

ストライド1024kBで何が起こっているのか。
----------------------------------
・stride 1024=1024*int=4kB
4kB毎にアクセスする→1 pageあたり一個のIntegerしか読まない。
つまり、全部で256 pageにアクセスする。
256 pageの命令でload/store命令を起こす。

つまり、
129個目をアクセスするときは、先客を追い出す必要がある。
よって、後半のアクセスはTLBは外れて追い出しながらアクセスしなくてはならない。

→よって、2回目以降の計測は、TLBがはずれまくるゾーンとなってしまう。


・stride 512 = 512*int = 2kB
→1 page(4kB)あたりにintegerが2個ある。
→128 page分のアドレスが作られる。
128 pageの空席がある。
→for loopなので、制御命令も含めると微妙に追い出されてしまうこともあるが、ほぼ全員座れる。
TLBは完全に満杯の状態だと右上がりに上昇する。

規則的な(64byte毎の)スパイクについて
stride 64:256kBおきにアクセスしている。
TLBに関しては問題は多分起きていないだろう
→他の理由があるはずだ。


さっきのアドレス表を思い出す。
PA 64
□□□□←6bit
↑6bit
全部で64×8=512 lines (entries)
つまりL1キャッシュに8つの座席がある?

64bit = int 16個分

-------------------
■■■■
-------------------
□□□□
-------------------
□□□□
-------------------
□□□□
-------------------
■■■■


4lineおきに使われる。→全てのlineが有効活用出来ない

最初:L1cacheを追い出しながらやる。
2回目の測定を始めると、後半を追い出しながら前半が入って息。
L1cacheの追い出し、追い出されが毎回起きている。
同様の理由で、stride 128とかも起こる。

画像を弄るときは1024*1024よりは1025*1025にした方が良い。
→2のべき乗は要注意

試験の話。
PC以外なら何でも持ち込み可能。

[質疑応答]
・2のべき乗の問題について
000/000000
100/000000
1000/000000
1100/000000

↑下位6bitは使われない。→使われないsetが存在する。

2008-01-14

Coming of Age Day

1/12からずっと数学Bの今まで溜まっていた課題レポートに着手して、ようやく終了!!

枚数にして42枚。 なんだこの清清しい爽快感はww



今年の数学の先生は、去年の先生に比べてメチャクチャ親切な人で、

課題レポートも、枚数は多いけれど、とても着手しやすかったのが嬉しい。



というか、

やはり、去年のT先生が異常だったことを実感。

もう二度と数学科専任教師とは関わりたくないわ。



しかし、ちょっと枚数多いんで、流石に全部を採点する時間はないだろうな。

せめて重積分のところだけでも採点してくれると嬉しいが。。。

う~、冬休み中に終わってれば・・・まぁそんなことを言っても仕方がないか。



あとは、フーリエ解析発展課題とプログラミング課題03で、今期の課題はコンプリートか。

もう数えるほどしかレポートがないぜ。嬉しすぎる。

さっさと終わらせて、試験対策に入るぜ。



追記:
タイトルとの関連性が0だったことに気付いたww

成人の日は上述の通り勉強です。式には行きませんでした。

でも、とりあえず毎年タダでなんか貰えるっぽいから、それだけ貰っておけばよかったと今更後悔。



"成人式"って言うと、侍魂ってサイトのコラム(信念)を思い出します。

http://www6.plala.or.jp/private-hp/samuraidamasii/sinnnenntop/seizinnsikinituite/seizinnsikinitite.htm

要約させてもらうと、成人式というのは、

主観的に大人になるのではなく、客観的に大人となる(=大人とみなされる)、

という感じだったかな。



成人式を終えて(行ってないけど)、成人になって…まぁ特に心変わりはないです。

とてもいつもどおりです。

理由は、侍魂の説が正しいならば、成人式が

"他人が自分への評価を変える"というだけのことだから。



"他人が自分への評価を(より厳しい方向に)変える"から自分を変える。

というのは、個人的にはありえない。

だったら今までのお前は一体なんだったんだよwww と自分に突っ込みたくなるから。

仮に成人になったから自分を変えよう、と思ったところで所詮は付け焼刃に過ぎないと思われ。




理系的に言い換えると、

既にモチベーションのベクトルRの傾きは十分に大きいので、

成人式という要素Sを加えてもR+S≒Rとなる。

という感じ。



…と、グダグダ書いていくとだんだん時間がなくなるので、今日はココまで。

続きはwebで。

P.S.
テスト終わったらアトレティコで成人祝い&新年会でもやろうかな。
忘年会を企画しておきながら、2年連続病欠は流石に萎える。


結論:テスト前に成人式出席は死亡フラグ。でも貰える物は貰っておけ。

2008-01-10

The Memory Mountain ver 2

(↑さっき計測したメモリマウンテン。Throughput≒3500。うちのPCはやれば出来る子らしい)

こんなもんかなぁ。

最後の方の計算式ちゃんとあってるんだろうか・・・ちょっと不安だ。

まぁ心配したところでどうしようもないか。

でもまぁ、今日でフーリエ実験も終わったし、CPEの計測も…まぁこれでpre完成ってことにして、

残るは、フーリエ発展課題と、数学B課題と、まだ見ぬプログラミング言語論課題03か。

さっさと終わらせて、期末対策に入ろう。

CPEの計測 ―行列N×Nの90度左回転― [図、表、ソースコードは省略]

目次
0. 動作環境
1. 実験内容
1.1 ドライバの作成
1.2 最適化の工夫をした関数を揃える
2. 実験結果
2.1 分割した場合の測定結果
2.2 他最適化に関する工夫の測定結果
3. 考察
3.1 最適化の観点から実験結果を解析/追加実験
3.2配列の上限要素数”ARRAY_MAX”とCPEの関係
4. 感想・まとめ
5. 参考資料
6. 添付資料
添付資料1 “ドライバex02a.cのソースコード”
添付資料2 “測定に用いたアルゴリズム(一部)”



0. 動作環境
本実験は全て、以下のCPUをもつノートPCで実験を行った。
(CPU-Zの実行結果と、mountain.cの実行結果を図示したもの)

/*picture is abbreviated*/


Clock frequency is approx. 1709.9 MHz

1. 実験内容
本実験は、以下の手順で行った。
1.1 ドライバの作成
1.2 高速化の工夫をした関数を揃える

1.1 ドライバの作成
 本実験では、以下の仕様を満たすドライバが必要である。
・ 行列N×Nを扱う2次元配列Matrix
・ Matrixを90度左回転するアルゴリズム
・ 任意のNに対してサイクルカウント値を測定し、その後CPE値を求める関数
よって、本実験を開始するために、まず上記の条件を満たすドライバを作成した。ドライバのソースコードは6.添付資料1に示した。
また、本実験で使用したプリプロセッサ・構造体・関数について、その仕様を以下に示す。

 -プロプロセッサ-
ARRAY_MAX
本プログラムにて用いられる、各配列の各要素の限界値を指定する。サイクルカウント値の測定結果の保存にも使われるので繰り返し回数(LOOP)以上の値をとることが望ましい。

 SPLIT
行列N×Nをいくつに分割するかを定義する。

 LOOP
関数func内で、サイクルカウント値を測定する回数を定義する。

 STANDARD
サイクルカウント値が観測された回数が「信用できる」と思える観測回数の定義。(ただし、本実験では結果の分散が激しかったので、“1”で観測した)


-構造体-
Matrix
行列N×Nを実現するためのint型2次元配列

Item
サイクルカウント値に関する情報を保存する構造体
doble cycle[ARRAY_MAX]
サイクルカウント値を保存する。
int count[ARRAY_MAX]
そのサイクルカウント値が観測された回数を保存する。


-関数-
void initialize(int a[], int N)
コマンドライン引数から得た値をNとし、行列N×Nの各要素に乱数を格納する。また、構造体の中身を初期化する。

 void showMatrix(Matrix m, int N)
デバッグ用関数。行列mの各要素を出力する

void showITEM()
Itemの内容を全て出力する。

void swapITEM(int i, int j)
Item a[i]とItem a[j]の内容を交換する。
void insertionSort()
Itemに対して、サイクルカウント値を基準とした挿入ソートを行う。

double getCycle(Item a)
Item aの中から複数回観測された小さな値を出力する関数。ただし、Itemの内容が既にソートされている必要がある。

int saveCycle(double cycle)
観測されたサイクルカウント値が初出ならば、そのサイクルカウント値を登録し、既出ならば、その出現回数をインクリメントする関数。

 void native_rotate(Matrix src, Matrix dst, int N)
行列srcを90度左回転させた結果を行列dstに格納する関数。

 void native_rotateA(Matrix src, Matrix dst, int line, int column, int N)
関数native_rotateを任意の数に分割して行う関数。例えば、行列64×64を8×8マスに分割した場合、各マスに対して計64回の90度左回転作業を行う。

void check_matrix(Matrix src, Matrix dst, int N)
行列dstが行列srcを90度左回転した行列と同じであるかどうかを確認する関数。

 void func(Matrix src, Matrix dst, int N)
行列srcの各要素を90度左回転させた位置に格納する。元の要素を上書きしないように、格納先は行列dstとする。また、この関数内で、サイクルカウント値の測定を行い、複数回観測された小さなサイクルカウント値を出力する。CPEはメイン関数で求める。

main()
仕様を満たすように各関数をそれぞれ実行していく。また、複数回観測された小さなサイクルカウント値を求め、そのCPEを出力する。

1.2 最適化の工夫をした関数を揃える
 今回の課題では、以下のアルゴリズムを用意した。

・ 課題説明のpdfに示された単純な関数
・ 行列N×NをX×X (X≦N)に分割して90度左回転をかけるアルゴリズム
本実験ではX=2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048を測定した。

上記のアルゴリズムの中から最も早いアルゴリズム”X×X”を見つけたら、次にその数値を使って、以下に示すような最適化の工夫を施した。右側には、施した工夫の説明を示した。

・ X×X in LF (Local Field) 測定に使う変数をlocal fieldにおく。
・ X×X invoked –O3 オプションの“O2”を”O3”に変えてコンパイル
・ X×X for文-Y 測定関数で使用されているfor文をY個減らす
・ X×X inc 変数lineまたはcolumnをインクリメントで表現する

本実験では、上記の手順に従い、各関数のサイクルカウント値を測定していく。そして、最も最適化できた関数を導き出す。
2. 実験結果
2.1 分割した場合の測定結果
行列N×Nを、X×Xのマス目に分割したときのCPE値について、以下の表1に示す。

表1.1 90度左回転の方法と行列N×NにおけるCPEの値
  行列N×N
64 128 256 512 1024 2048
Function Normal 14.35 14.43 15.37 19.02 112.15 126.29
partition 2×2 15.80 17.29 17.89 24.80 62.28 65.64
partition 4×4 8.56 9.23 10.36 13.27 31.99 34.35
partition 8×8 7.33 6.61 6.27 11.21 27.45 29.43
partition 16×16 14.25 13.92 13.96 17.70 21.94 22.58
partition 32×32 14.08 13.79 13.81 17.78 19.74 20.07
partition 64×64 14.20 13.87 13.75 17.69 18.91 19.36
partition 128×128 NaN  13.96 13.84 18.31 19.20 19.82
partition 256×256 NaN  NaN  13.86 18.64 19.38 19.96
partition 512×512 NaN  NaN  NaN  18.94 20.71 21.80
partition 1024×1024 NaN  NaN  NaN  NaN  113.78 114.00
partition 2048×2048 NaN  NaN   NaN NaN  NaN  124.66
※ 赤文字は最も早いCPE値

表1.1から分かること
・ N=64, 128, 256, 512においては行列を8×8マスずつRotateさせたほうが早い
・ N=64, 128, 256, 512においては行列を64×64マスずつRotateさせたほうが早い

表1.1を折れ線グラフで表示させたものを以下の図1.2に示す。


図1.2から分かること
・ 行列512×512から1024×1024にかけて、急激にCPEが大きくなる
・ 64×64に分割するとCPEの線がほぼ並行になる


図1.2の0 <>

図1.3からわかること
・ N=256からN=512にかけて、どの折れ線も若干CPE値が大きくなっている
・ N=1024からN=2048にかけて、どの折れ線もほぼ水平になっている
・ X=64の折れ線が、最も水平に近い折れ線になっている。


以上の結果より、各行列N×Nに対して、最も適切な分割X×Xは以下の通りとなった。
行列64×64  → 分割8×8
行列128×128  → 分割8×8
行列256×256  → 分割8×8
行列512×512  → 分割8×8
行列1024×1024 → 分割64×64
行列2048×2048  → 分割64×64




2.2 他最適化に関する工夫の測定結果
実験2.1の結果からN=8, 64に絞り、様々な最適化の工夫を施して、CPEの計測を行った。その結果を以下の表2に示す。

表2. 8×8または64×64に高速化の各工夫を施したサイクルカウント値
  行列N×N
64 128 256 512 1024 2048
function partition 8×8 7.33 6.61 6.27 11.21 27.45 29.43
partition 64×64 14.20 13.87 13.75 17.69 18.91 19.36
8×8 in Local Field 6.92 6.64 6.34 11.54 27.15 29.31
64×64 in Local Field 14.20 13.82 13.75 17.65 18.83 19.29
8×8 invoked -O3 in LF 7.02 6.34 6.12 11.28 27.23 29.56
8×8 for文-1in LF 6.62 5.96 5.65 10.72 26.91 28.83
8×8 for文-2 in LF 6.47 5.83 5.49 10.70 26.94 28.80
8×8 for文-2 in LF and Matrix in LF 6.57 5.88 7.01 14.10 27.44 29.20
8×8 for文-2 in LF and increment 6.54 5.87 5.50 10.75 27.05 28.83
8×8 for文-2 in LF and inc at Array 6.52 5.84 5.53 10.71 27.24 29.11
※赤文字は、最も小さいCPE値

表2の結果から、各Nに対して最も小さいCPEを返すアルゴリズムは以下のようになった。

行列64×64  → 分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列128×128  → 分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列256×256  → 分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列512×512  → 分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列1024×1024 → 分割64×64 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列2048×2048 → 分割64×64 + for文の内側2つを崩し、変数をLocal Fieldに置く



3. 考察
3.1 最適化の観点から実験結果を解析/追加実験
 今回の実験結果から、最適化できた箇所と出来なかった箇所について、キャッシュサイズを考慮しながら考察していく。また、考察を通して試してみたい方法を見つけたら、その都度実験を行い、その結果を示していく。
まず、表1.1の実験結果を通して判明した最適化の法則と、その理由を以下に挙げる。
・ 分割回数は引数ではなく#defineの方がよい
→#defineは単純な置換なので、変数を呼び出す手続きを減らすことが出来る。

・ for文の内側で関数を呼び出さないほうが良い
→関数を呼び出す手続きにも、サイクルが必要になるから。

・ O3よりO2オプションの方が良い
→O3はO2の各オプション機能に加えて-finline-functions, -fweb, -frename-registersが追加され、これらのオプションが最適化に対して改悪となっているから。

・ int sepN=N/SPLITという変数は用意せず、直接N/SPLITを使った方がよい。
→sepNという変数用にメモリを割り当てなくてはいけないから。一方でint Nは最もよく使われる変数なので、大抵の場合は既にCPUに近いメモリに入っている。よって、sepNを用いる場合と違い、無駄なメモリ領域を使わずに済む。

・ for文のネストする回数は出来るだけ減らした方が良い
→for文を呼び出すためのサイクルが必要になるから。
また、キャッシュにうまく乗る可能性が増えるから。

・ static MatrixはLocal Fieldに置かない方がよい
→Matrixの内容をコピーするサイクルが追加されるから。

・ column++よりcolumn+Xの方が若干早い
→即値アドレスで実現できるので、サイクルでの差はあまりないから。
 インクリメントなので、columnの値が毎回書き換えなければいけないから。
 Columnを書き換えた値を元に戻す作業が必要になるから。

・ 配列内でインクリメントしても、あまり最適化できない
→同上の理由で、インクリメントした方が若干サイクルは早くなるが、逆に無駄なサイクルも必要になってくるから。

次に、表1.1において、行列N×NをX×X分割したときの最適化について考察したい。
実験結果の表1.1を見ると、明らかにキャッシュに乗っていないnormalや2×2分割アルゴリズムと最も早かったアルゴリズムのCPEを見比べると、ほぼ全てのN×N行列のMiss Rateを抑えることに成功したと分かる。特に、N=64, 128, 256の部分については、CPEが3~8の範囲に入っていることから、Miss Rateも限りなく低い割合になっていることが分かる。
 一方で、N=512, 1024, 2048の部分については、元の単純なアルゴリズムと比べると、確かにMiss Rateは下がったといえるが、CPEが3~8の範囲を多少超えているところを見ると、まだまだ改善の余地は残っているように見える。

 そこで、N=512, 1024, 2048に焦点を当てて、Miss Rateをさらに下げることができないか検討してみた。
そこで、まずは表1.1を参考にして、行列N×Nと分割X×Xの効率の良い比率を調べた。結果を、以下の表3に示す。
表3. 行列N×Nの容量を分割X×Xの容量で割った値
  行列N×N
64 128 256 512 1024 2048
分割X×X (容量[Byte]) 行列N×Nの容量[Byte] 16,384 65,536 262,144 1,048,576 4,194,304 16,777,216
2×2 (16) 1024 4096 16384 65536 262144 1048576
4×4 (64) 256 1024 4096 16384 65536 262144
8×8 (256) 64 256 1024 4096 16384 65536
16×16 (1,024) 16 64 256 1024 4096 16384
32×32 (4,096) 4 16 64 256 1024 4096
64×64 (16,384) 1 4 16 64 256 1024
128×128 (65,536) NaN 1 4 16 64 256
256×256 (262,144) NaN NaN 1 4 16 64
512×512 (1,048,576) NaN NaN NaN 1 4 16
1024×1024 (4,194,304) NaN NaN NaN NaN 1 4
2048×2048(16,777,216) NaN NaN NaN NaN NaN 1
*赤文字は表1で最も小さいサイクルカウント値が出た位置
表3の結果から、各要素Nに対して最もMiss Rateをうまく抑えることのできた部分(文字部分)を見ると、分割後のマス目の数は64~4,096あたりがMiss Rateをうまく抑えられる範囲だと理解できる。また、N=64,128,256,512の赤文字部分と、N=1024,2048の赤文字部分が横並びになっていないことから、前者と後者の乗っているキャッシュレベルは異なっているのではないかと推測できる。
 これらの結果を元に、N=512, 1024について、行列N×Nを分割するXの値を、多少変化させて再度CPEの結果を行った。また、方針としては、表3の結果から、N=512についてはXを大きくする方向に動かしていき、N=1024についてはXを小さくしていく方向に動かしていくことにする。
その結果を以下の表4.1, 4.2に示す。ただし、SPLITの値で行列Nをうまく分割しきれるように、Nの値は適宜変更させてある。

表4.1 行列N×NをX×Xで分割したときのCPE値(1)
行列N 511 513 510 517.00 516.00
分割X 7 9 10 11 12.00
CPE 11.34 11.77 13.37 15.37 16.11

表4.2行列N×NをX×Xで分割したときのCPE値(2)
行列N 1035 1029 1000 1020 1045
分割X 45 49 50 51 55
CPE 19.05 18.94 18.64 18.88 18.69

 表4.1, 4.2を見ると、特にMiss Rateが小さくなった箇所見られない。よって、SPLITの値を変化させていってもこれ以上Miss Rateを小さくすることは難しいことがわかる。また、Conflict Missの観点から、多少キリの悪い数字を考慮しながらSPLITの値を決めたが、それもあまり功を成さなかった。つまり、Capacity Missに目を向ける必要がある。言い換えれば、N=512, 1024, 2048について、さらにMiss Rateを小さくするためには、notive_rotateAのアルゴリズム自体を見直す必要がある。

 そこで、まずはUnrolling 8を試してみた。ただし、N=512と1024, 2048ではキャッシュレベルが違う可能性があるので、今回はN=1024と2048にのみ焦点を当てた。加えて、代入する順序を逆順にする方法、lineとcolumnを逆にする方法も試してみた。結果を以下の表5に示す。
表5. N=1024, 2048に各工夫を施したCPE値
  行列N×N
1024 2048
現時点での最速値 18.83 19.29
unrolling 8 18.93 19.39
unrolling 8 reverse 18.99 19.42
column⇔line 12.07 12.16
 表5を見ると,unrolling 8, unrolling 8 reverse共にあまり良い成果は出なかったが、columnとlineについては大幅にMiss Rateを小さくすることに成功した。これは、メモリ領域には横にアクセスしていくよりは、縦にアクセスした方が早いことを表している。
 ここで、他のNの値に対しても同様の方法でMiss Rateをさらに下げられるのではないかと考え、この方法を用いて再度計測しなおした。その結果を以下の表6に示す。
表6 アクセスする順を縦横反転した場合のCPE
  行列N×N
64 128 256 512 1024 2048
function 現時点での最速値 6.47 5.83 5.49 10.70 18.83 19.29
partition 2×2 10.10 10.94 11.16 23.58 73.96 73.50
partition 4×4 6.41 6.69 6.70 15.96 35.54 37.70
partition 8×8 5.25 4.98 5.00 15.88 23.89 25.03
partition 16×16 5.72 5.37 5.26 13.42 15.91 16.91
partition 32×32 6.88 6.56 6.68 12.52 12.78 13.03
partition 64×64 6.64 6.41 6.47 11.43 12.02 12.18
partition 128×128 NaN 9.22 9.14 12.81 13.62 13.50

表6から、N=512を除いた全てのNは、やはり縦横反転したほうMiss Rateが小さくなることが分かった。ちなみに、N=512に対して望んだ結果が得られなかったのは、N=64,128,256とN=1024,2048の各キャッシュレベルを跨いでいることが原因ではないかと伺える。

 以上の結果から、行列N×Nに対して、要素1つあたりにたいするサイクルカウント値を最も小さくする方法は、以下の通りになった。

N=64 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=128 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=256 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=512 → 行列を8×8マスずつに分割して、※2の方法でsrcにアクセスする。
N=1024 → 行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
N=2048 → 行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。

※1 Matrix src [A][B]にアクセスするときはfor文の最も内側でAにアクセスし、外側のfor文でBにアクセスする
※2 Matrix src [A][B]にアクセスするときはfor文の最も内側でBにアクセスし、外側のfor文でAにアクセスする
3.2 配列の上限要素数”ARRAY_MAX”とCPEの関係
 2008年1月9日の講義でARRAT_MAXとCPEの関係を聞いたので、その知識を元に考察3.1の結果を掘り下げて、再度実験と考察を行っていきたい。

 まずは、授業中に言われていた、ある突出した地点と現在のARRAY_MAXの地点が重なっているのではないかと考えた。その部分を検証するために、ARRAY_MAX=2048の値を少し変更して場合のCPE値を調べた。その結果を以下の表7に示す。

表7 分割8×8におけるARRAY_MAXとCPEの関係
  行列N×N
64 128 256 512 1024 2048
ARRAY_MAX 現時点での最速値 5.25 4.98 5.00 10.70 12.02 12.18
2045 3.91 4.24 4.26 5.95 9.53 Corrupt
2046 4.36 4.56 4.67 7.37 9.92 Corrupt
2047 4.88 4.87 6.12 8.14 9.97 Corrupt
2048 5.25 4.98 5.00 15.88 23.89 25.03
2049 5.06 4.81 4.61 6.82 10.20 10.50
2050 4.97 4.73 4.53 6.84 10.12 11.84
2051 4.35 4.37 4.33 6.50 9.63 9.95
2052 4.15 4.24 4.17 7.03 10.17 10.30
2053 4.06 4.17 4.27 6.28 9.60 10.07
2054 3.95 4.13 4.24 6.46 9.66 10.26
2055 3.99 4.11 4.23 5.82 9.46 10.18
2056 3.97 4.08 4.30 6.28 10.26 12.01
2057 3.94 4.00 4.25 5.81 9.52 10.47
2058 3.91 3.92 4.20 6.26 9.66 10.15
2059 3.91 3.88 4.22 6.03 9.94 10.50
※ 赤文字は最も表の各列中で最も早かった箇所

結果は、予想したとおりであった。表7から今まで使っていたARRAY_MAX=2048の部分だけ明らかに突出した結果が出ていることがわかる。これはつまり、ARRAY_MAXにキリのよい数字を使っていたが故に、満遍なくキャッシュを活用出来ず、キャッシュの同じ場所に何度もアクセスされたと考えられる。言い換えれば、ARRAY_MAXをキリの悪い数字にすることで、キャッシュに満遍なくアクセスさせることが出来たといえる。

ここで、ふと疑問に浮かんだのが、”ARRAY_MAXの値と分割X×Xは相互に依存しているかどうか”という点である。それを確かめるために、ARRAY_MAXを2059に固定し、分割X×Xを変数として再度実験を行った。その結果を以下の表8に示す。

表8 ARRAY_MAX=2059における分割X×X
  行列N×N
64 128 256 512 1024 2048
function 現時点での最速値 3.91 3.88 4.17 5.81 9.46 9.95
partition 2×2 9.27 9.60 10.29 14.09 16.57 16.58
partition 4×4 5.56 5.66 6.26 8.25 10.15 10.69
partition 8×8 3.91 3.92 4.20 6.03 9.94 10.50
partition 16×16 3.15 3.13 3.25 5.98 10.23 10.60
partition 32×32 2.91 2.88 2.90 6.96 10.61 10.69
partition 64×64 2.80 2.80 2.80 6.99 10.92 11.30
partition 128×128 NaN 5.09 5.31 8.95 12.45 13.00
※ 赤文字は最も表の各列中で最も早かった箇所

表8からARRAY_MAXを2059に変更すると、今まで分割8×8のとき早かったN=64, 128,256の部分が分割64×64で最も早くなるという結果が出た。また、今まで64×64が最も早かったN=1024,2048が分割8×8のとき早くなるという結果が出た。
このことから、少なくともARRAY_MAXの値と分割X×Xは相互に依存している関係、ということが分かる。言い換えれば、各ARRAY_MAXの値に対して、それぞれ分割X×Xの計測を行わないと、最も早いCPEは分からないということになる。

しかし、現在使用しているドライブではそこまで大規模な実験は出来ないので、表6,7,8から、ある程度目星をつけた部分にのみ計測を行った。結果を以下の表9に示す。

表9 表6,7.8から気になるところのCPE値
N ARRAY X×X CPE 結果
256 2052 64×64 2.84 ×
256  2052 32×32 2.93 ×
512 2057 8×8 5.78 ○
1024 2055 8×8 10.18 ×
2048 2051 8×8 9.98 ×
※ 赤文字は今までのCPEより早かった箇所
今回の計測で更新されたCPEはN=512の部分だけである。しかし、更新前との差が0.03しかないところも踏まえると、あまり”結果を出すことが出来た”とはいえない内容である。CPEの最適化とは関係ないが、この結果からCPEの計測では帰納的な計測方法ではなく、なるべく演繹的な計測方法の方が効率的だと分かる。


 以上、今回の考察/結果をまとめると、以下のようになる。
・ ARRAY_MAXが2^N乗ではスパイクと重なっている場合が多い。スパイクと重なっている場合は、重なっていない場合と比べMiss Rateが非常に大きくなる。
・ CPEはARRAY_MAXの値をインクリメント、またはデクリメントしただけでも大きな変化を示す。
・ ARRAY_MAXの値と分割X×Xは互いに依存していて、ARRAY_MAXの値を変えると最も効率的な分割Xの値も変わる。
・ CPEの計測は帰納的ではなく、演繹的に行った方が結果は出やすい。

また、今回の考察を通して、Nの各値の最も早いCPEとその状態は以下のようになった。

[N=64, CPE=2.80] ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=128, CPE=2.80] ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=256, CPE=2.80] ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=512, CPE=5.78] ARRAY_MAXを2057と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
[N=1024, CPE=9.46]  ARRAY_MAXを2055と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
[N=2048, CPE=9.95] ARRAY_MAXを2051と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。

※1 Matrix src [A][B]にアクセスするときはfor文の最も内側でAにアクセスし、外側のfor文でBにアクセスする

 今回の実験の最終的な成果は上記のような結果となった。

ここで、相対的に今回の実験結果が良い結果だったのかどうかを見分けるために、メモリマウンテンの結果から行列のCPEの概算を算出し、考察したい。

動作環境で示してあるメモリマウンテンを見ると、working set sizeが16kBのとき、L1キャッシュに乗り、Z軸のread throughputからうまくいけば約3,250[Mb/s]程の性能を出せるはずである。つまり、今回の実験のN=64(16kB)とき、L1キャッシュにうまく乗せることが出来れば、以下のCPEを出すことが出来る。

周波数=1,709,000,000[cycle/s],容量=16,000[byte],Throughput=3,250,000,000[byte/s]より、16kBを読むのに必要なcycle = (周波数×Throughput / 容量) = 8,42[cycle] となる。
ここで、N=64のとき要素の数は64×64= 4096なので、1要素あたりに必要なcycleは
8,417 / 4,096 = 2.06[cycle]となる。

ただし、ここで考慮しなくてはいけないことは、メモリマウンテンのスループットはreadに対するスループットなので、read以外のcycle数は考慮されていない、ということである。しかし、これは言い換えれば、行列の1要素あたりに必要なサイクル数は2.06+α(α=read以外にかかるサイクル数)となるので、理想のCPE≒2.06と、概ねの目安を立てることができる。

同様にして、他の各Nの値に関しても計算してみると、
N = 128 → CPE = 2.34+α
N = 256 → CPE = 2.34+α
N = 512 → CPE = 2.34+α
N = 1024 → CPE = 2.84+α
N = 2048 → CPE = 2.97+α (mountain.cを拡張して求めた)
となった。
上記の計算値と最終的な実験結果を比較すると、今回の実験の最終結果はN=64, 128, 256については、ほぼ理想の状態に近づけることが出来たといえる。一方でN=512, 1024, 2048とNが増えていくにつれて、キャッシュにうまく乗せることが出来ず、Miss Rateが増えた、と推測することができる。つまり、N=512, 1024, 2048については、まだまだ改善の余地が残っている、と分かる。


4. 感想・まとめ
今回の課題を通して、CPUに関する知識を掘り下げられたのと、コンピュータアーキテクチャの勉強、またTechnical Termを学ぶことができたのは、とても良かったと思う。
ただ、実験中とても疑問に思ったのがメモリマウンテンの結果が、日をおいて実行すると大きく異なる値を示すことである。本レポートでは、3000[MB/s]のスループットが実行結果として出たものを使用したが、場合によっては600[MB/s]のときもあった。処理速度は”偶然遅くなることはあっても、偶然早くなることはあまりない”という特徴があるので、3000[MB/s]を採用したが、何故そこまで差が出るのか、という考察もいずれ行いたい。

5. 参考資料
CPUID(CPU-Zの製作元)
http://www.cpuid.com/

添付資料1 “ドライバex02a.cのソースコード”
添付資料2 “測定に用いたアルゴリズム(一部)”

2008-01-09

The Memory Mountain

              My Memory Mountain ↑     
↓Sample Memory Mountain(2002) 

…え~と、2007年購入のMy notePCは2002年のPC(sever)に2倍以上の差で負けますたorz
しかし、先生のノートPCは3,200だったよな…。これが一般人と研究者のスペックの差かorz orz
フーリエ課題は終わったけど、発展課題もやっておかなくてはな。

でも、解析学は若干苦手だ。。。

ということで、フーリエ解析の発展問題は、一旦置いておいて、ほかの事をやってみるテスト。
結果:
プログラミング言語論(課題+発展提出)、CPE計測(追加考察&校正終了)、
MIT lecture summary(これ以上のdownsizeは無理ぽorz)


[reference:"Computer Systems: A Programmer's Perspective" (CS:APP)]
プリント(A3)2枚
・Class14
・Class19(2002)/16(2006)
・Class20(2002)/17(2006)

(.../opt)
☆.../mem/mountain/mountain.c

warm upと
各strideの実行と
その結果表示を
同時にやってくれるプログラム。

Excelに出力させると、とてもわかりやすい。
教科書の著者はさらに、グラフを作っている。
→上2行を省けば、ほぼ等高線に近いグラフになっている。


・図に関して、
ストライドは"s1, s4, ... ,s22まで
容量は32m, 512k, 8k

→メモリの性能は、アクセスする幅によって、大幅に変わる

ゲレンデみたいなところ(右側中部)で、プログラムがかけると嬉しい。
谷底みたいなところには、出来ればいきたくない。


・L1cacheにのると、メモリマウンテンの一番高いところの性能が出る
・L2は真ん中のゲレンデあたりの性能が出る。
・キャッシュから外れると谷底。
→ストライドが小さいと中々性能が良い。
→何故→1回はずれると、あとの7回が当たるから。


・メモリマウンテンは眺める角度を変えることが出来る
裏面から見ると、実は崖になっている。
つまり、アクセスする幅が少なすぎるとそれはそれでマズイ。

2002年頃の性能結果(講義資料:server)→1MB/s
現代のPCの性能結果(先生のノートPC)→3Mb/s
つまり、当時と今では、3倍ぐらい早さが違う


・メモリマウンテンの一番左側のラインをプロットすると、そこの局所性が分かる。
→結果:明らかに3つのゾーンがあることが分かる。
S1から順番に[キャッシュはずれ, L2, L1]で早くなっていく?※要確認


・真ん中のゲレンデのところ
→S1からS16に向けて段々遅くなっていく。
始めは、つまり、一つの要素が外れると7つがうまくいく
グラフ右側のフラットな部分は、一個の部分を読み込んで他の部分を読み捨てている。
→もったいない!!


・真ん中のslope→降りる場所はs16
1キャッシュラインに16個のキャッシュがある?


・メモリマウンテンを見ると1次キャッシュ、2次キャッシュが明確に分かる。
→一番右側奥のstrideを大きくすると隆起した部分は、現段階ではとても難しい話でまだ説明できない。


・東大、Quad coreのopteron搭載の国内最速スパコン。(日立協力)
~約15,000コアで理論ピーク性能140TFLOP
→作るのは簡単。つなげればいいだけ。
ただし、2.3Ghzを4個(16コア)搭載したものを繋げる。→これは難しい。
先生の研究室もそれを買おうとしている?


・AMD's "TLB"について
年末に売り出そうとして、延期になっている。→株価下落。
論理設計にミスがあることが分かった。
opteron2.3Ghzは世の中にはまだ売り出されていない。
Bug in AMD's quad-core Barcelona and phenom may be more serious than previously suspected.
→そのバグは結構重大だぞ。といっている。


・Quad-coreのメモリ性能?
・メモリ性能はそんなに変わらない。
・最上部がフラットになっている(3Mb/s)
・L2のスキーヤーゾーンっぽい傾斜が長い。
・スロープがさらにもう一個ある→L3がある。
・ゲレンデだとCPUのコアが独立で出来る?

バグフィックスのために今の性能より、若干性能が落ちると予測できる。

→課題はなるべく谷底には行かないようなプログラムを作ってね(はぁと。



・2次元配列のコピーについて
srcからdstにコピーする。
→for文外側の添え字配列の左側に、
for文内側の添え字配列の右側に送ったほうが早い
(常識らしい)

まともなプログラム CPE=14.10 (ただし、最適化は行っていない)
うっかり添え字を逆にしたプログラム CPE=370
結果:20倍性能が違う

・本当にそれほど遅くなるのか?実験してみる
ためしに配列のサイズARRAY_MAXを一つ大きくしてみる 2048→2049 ←※重要
→うっかり間違えプログラムを実行
結果:CPE=34.57

つまり、配列の要素を2^Nで確保すると、悲惨なことが起こる
[例2]1024で下手なプログラムを書く 結果:CPE=300
1023で下手なプログラムを書く 結果:CPE=27
→何故このような結果が出るのか考えてみる→課題の考察に追加で書いた方が良いっぽい?


・今度は違う形で実験
メモリマウンテンでは3200万個ぐらいアクセスするけど、

今回は、アクセス256個、ストライド1~1400まで(1024を包括するため)で実験してみる。
直感では全部キャッシュに乗る、はず。
どんなへたくそなプログラムでも、256個のintegerデータなら
全て1次キャッシュに乗る、はず。
結果;256個の一回分のクロックサイクルを見ていくと
前半:大体600付近 + ところどころ1600の突出がある(スパイクと呼ぶ)
後半:ほとんど1600になる

→何故かこのような結果になるのか?

・グラフにしてみる
結果:arc tangentみたいなぐらふ?
序盤 = フラット+ところどころにスパイク(64の倍数の定期的なスパイク + 不定期なスパイク)
中盤1= 右肩上がり(大) + ところどころのスパイク
中盤2= 右肩上がり(中) + ところどころのスパイク
終盤 = とても遅い数値のフラット+(スパイク?あったけ?うる覚え)



・opteronの場合。
この実験をすると、いいプログラムは CPE=600 → これはよい
また、悪いところ(終盤)でも2倍ぐらい → まぁよい

!!ただし!!
・あちこちでスパイクの不定期な頻出と定期的な頻出が出ている。
特に、1024の部分が"とんでもなく遅い"
また、512の部分が"とても遅い"

ModernのCPUだとこれだけ複雑な結果がでてくる。
下手な数(つまり、キリのいい数)を書くと、
スパイクに当たってしまい、非常に遅いプログラムになる可能性がある。
また、逆に考えれば、メモリアクセスの管理は恐ろしく複雑なことをやっていることが分かる。

*2006年版の資料の方が2002年版より分かりやすいらしいよ。



【仮想記憶について】
CPUから効率的に取る必要がある。
複雑なロジックだからAMDの人もバグに苦労してしまった。

※CAUTION ※
!!ここら辺からちょっと教室がうるさくなったので、聞き逃し部分がある!!
!!講義資料とノートを比較して、事実を確認した方がよい       !!

消費電力を少なくする。
→これだとサーバーの世界には勝てない。
・講義:Virtual Memory
来年はOSの授業がある→そこでも仮想記憶について触れる→その予習と思って聞いてほしい。

機械語の命令なので番地がある。
メモリの番地とその番地が同じであるかというと、そうではない→バーチャルな番地がある
→4100番地でも4100番地にいくとは限らない。

つまり、キャッシュには無くても仮想記憶にはある場合がある。
desktopやlaptopはほとんどこんな感じ。
→仮想記憶はとても偉大なアイデアだ、と著者は述べている。


[Address Spaces]
この授業は3年前に大幅に模様替えした。
なぜなら、そのころはCPUのアドレスは32bitだった
しかし、今はcore2やopteronだと64bitになった。
→大きなアドレスに触れるようになった。

例えば、積んでいるメモリ1Mでも、最低メモリ4MB必要な動作を行うことが出来る。
→どうして?
→Nがバーチャルなアドレススペースとなる。
→Mはフィジカルなアドレススペース(物理アドレス)
32bit→4GB
64bit→4GB×2^32(=約40億)

→64bitだと仮想記憶はいらないのでは?

では、何故使うのか。

→"性能を超えたプログラムでも動かすことが出来る!"

Main memory is a chache for rhw contents of a virtual address space stored on disk
→必要に応じて読んだり読みこなかったりする。

読み書きしちゃいけないメモリを触ってブルースクリーンになることはよくある。

記憶管理には慎重に。→あるプロセスはメモリ領域を勝手に読み書きしてはいけない。

中にはOSの秘密な情報があったりする。→勝手に読み込まれては困る

[1]は効率、[2][3]はOSについての話
今回は[1]について重点的に話していく。

・仮想記憶の空間があって、ある程度大きい。
→バーチャルメモリは、どこの物理メモリがのっかっているか、という情報を持っている必要がある。


理論的には通じるけど、定常的には変わってくる。→プリントP.7
キャッシュに乗るプログラムとならないプログラム。
一般的に
キャッシュ → SRAM
メインメモリ→ DRAM
DRAMにも乗らないところ → DISKに行く (この場合、性能は10万倍ぐらい違う)
となっている。

EX.レポート書きながらエクセル,音楽,画像弄くるなどをやってると、
全体のメモリ量はバカにならない。同時に実行すると、急に遅くなる。
これは、全体としてメモリに乗らないので、ある仕事に必要な容量はDisk間とやりとりしてしまう
→動作が遅くなる and "disk"がカタカタ音を出し始める。これを”Thrashing”という
→補足:よってThrashingが起こる=とても動作が遅くなる。

メモリとDiskのやりとりは 4 or 8 KBが典型的
一個のキャッシュライン
→3号車のどこに目的の値があるか探すのが大変。
すきなモノが好きなフィジカルページに行ける。
いける場所は多少限られている。

any virtual page can be places in any physical page.
メインメモリとDiskのreplacement algorithmsは複雑。
メインメモリにすぐに書き続けていくと、大変
メインメモリには反映させるけどDiskまでは反映させない。遅いから→write-back方式 を採用?

virtual memory(disk上にある)
仮想的にDiskにある。
実際に積んでるメモリ→physical memory(DRAM)

ページテーブル。4kBの単位で管理/情報の受渡が行われている。
nullは全然使ってない。
物理なのか仮想なのかどこに乗っかっているかを管理するところ。→必ずある。

乗ってたらページヒット。
プログラムが見にいたアドレスがDiskにある→"ページフォールト"→これが遅くなる理由
メインメモリに乗っていないところにアクセスした場合のこと。


大体何やっているか→プリントP12
"DMA" = direct memory access
DisKを一旦メモリのおいて、その後processorから読み取る。よって、とても遅い。

【大事な言葉集】
VM
Page failt
DMA
working set
Thrashing


同時に使う総量はたいしたことがない。
プログラムの実行中のある時点の前後0,何秒ぐらいでは、
バーチャルページのいくつかの選ばれた場所、部分集合にアクセスする。
(部分集合→ワーキングセット?)

ワーキングセットがメインメモリより小さければ、最初はミスするけど、その後は良い性能が起こる。

・メモリマネジメントの話。OSの話なので省略
・残りの話→最終回

【期末試験について】
日付、1月30日
資料持込可、基本的には何でもOK(パソコン不可)。
CS:APPの講義スライドのコピーも持ち込みか
(持ち込むことを進めます)
試験範囲は授業で扱った内容
・配点
期末試験:約50%
レポート:約50%

2008-01-08

Call-by-Need, 関数ポインタについて

発展問題のCall-by-Needが完成!

しかし、今日はフーリエ懐石のマスマティカまで手が回らなかった。
やっぱ学校始まると、授業の文だけ課題をこなす時間が少なくなるからか。
それに授業に集中する分の体力も減ってしまうし。。。

残り一ヶ月の追い込みスケジュールに支障が無いように、そこらへんは要チェックしないとな。



[Call-by-Need]
Call-by-Nameを改良(?)してできた引数受渡機構。
Call-by-Nameが毎回借り引数が来るたびに式を評価するのと違い、
一度仮引数を評価したら、その評価値をその後の式に適応させていく。

>>外側の関数適用を先に評価
>>同じ式は1回だけ評価、結果を使い回す
>> let f x = x * x in f (5 + 3)
>>→ f (5 + 3)
>>→ (5 + 3) * (5 + 3) # 2つの (5+3) は同一
>>→ 8 * 8
>>→ 64
>> cf. “Haskell” (Call by need な関数型言語)

„ 利点
„ 計算能力が高い (call by name と同じ)
„ 1つの式の評価は1回で済む
„ 欠点
„ 実装が遅くなる
„ 式の評価タイミングは依然制御困難
„ Sharing があるのでさらに複雑に

(refer to the lectue "ML" Univ of Tokyo)

よって、例えば
int x=3, y=5, i;
for(i=0; i<100 ; i++) numlist[index] = index;
func(x, numlist[x*y]);
echo 「"numlist[X] != X"となっている部分を出力する」;

func(int a, int b){
a += b;
i++;
j++;
b += 30;
}

※処理系は脳内コンパイラ。

とすると、出力結果は
numlist[15] = 45
となる。



[関数ポインタについて]
関数も変数と同様に名前を持ち、その実体(命令列/データ)は
メモリ上に格納され、その格納領域を指し示すための参照が、
関数名/変数名に割り当てられる
「フォン・ノイマン・アーキテクチャ」において、
データと命令はどちらもメモリ上に格納されるバイト列になる。

したがって、関数/変数の実体の格納位置をポインタで
表現するCでは、関数のポインタを扱うことができる。
つまり、関数ポインタ値を代入できる変数が宣言できる

int型の変数mと、int型のデータへのポインタ変数
nの宣言
intを返す関数fと、intへのポインタを返す関数gと
intを返す関数へのポインタ変数hの宣言
int m;
int *n;
int f();
int *g();
int (*h)();

[reference: the Lecture of "PLT", Waseda University]

2008-01-07

Call-by-*

冬休みは今日で最後です。結局数学Bが…orz

まぁ期限はまだまだ先なんで、期限にさえ間に合えば別に評価が変わることはないんですが、

なんか自分に負けた気分だ...orz orz orz



というか、実際は各教科の予習復習も、電子回路/プログラミング言語論の過去問も

手を付けられなかったわけだし…駄目人間過ぎるわ。

さらなる時間圧縮をするしかない。





[前提]
#define NUMLISTSIZE 100
for (index = 0; index i = 5;
j = 6;
k = 3;
func(k, i, numlist[i*j]);


[Call-by-Value]
・実引数をcallerの環境で評価
・その評価結果のコピーを仮引数に代入してcalleeを実行
・仮引数の値が変更されても、対応する実引数には影 響しない
・大域変数など、引数で渡されないcalleeのスコープ外の変数を変更すれば、
callerの環境に影響する

func関数の引数には、各引数の値を呼び、別々の変数として扱う。
一般的な使い方。


[Call-by-Value/Result]
・実引数をcallerの環境で評価
・その評価結果のコピーを仮引数に代入してcalleeを実行
・calleeから復帰時に仮引数の値を実引数に代入
・仮引数の値が変更されると、対応する実引数に影響する
・復帰時におけるコピーは、
RHVの評価にはcalleeの環境を、
LHVの評価にはcallerの環境を用いる
ex.入力時にs[i*j(=3)]のとき
× s[3]=n
○ s[i*j]n
となる。また、×の復帰方法を、Call-by-Copyと呼ぶ。

*問題点
Call-by-Value/ResultはALGOL Wなどで採用されたが、
機構が複雑になるため処理系の実行効率が悪いため、
他の言語で採用されることはほとんどなかった

func関数の引数には、各引数の値を呼び、別々の変数として扱う。
ただし、func関数の動作後、引数から得た局所変数の結果を、引数に返す。

*func関数動作後の式の評価は、その瞬間の変数によって左右されることに注意する。
→cf. numlist[i*j] = Ncopy;


[Call-by-Reference]
・実引数をcallerの環境で評価
・その評価結果の参照(reference)を仮引数に代入してcalleeを実行
・仮引数の値が変更されると、対応する実引数に影響する

引数には変数のメモリ番地を呼び出して使う
→func関数内で引数が書き換えられた場合、そのメモリ番地を書き換えてしまう
→func関数に引数として与えた変数の値が変わる可能性がある。
cf.ポインタ


[Call-by-Name]
・実引数を評価せずに、式のまま仮引数に代入する
・実引数とともに、その実引数を評価するのに十分な、
callerの環境の部分集合も受け渡す
・式とその評価に用いる環境の組を、閉包(closure)と呼ぶ
・calleeの中で仮引数を評価するたびに、仮引数に代 入された実引数を、
閉包に与えられた環境を用いて評価する


printf("N=%d\n", (N));\
// N==numlist[i*j]
例えば、上式の場合、式が呼び出された瞬間のiとjの値が呼び出される。
このとき、i=11, j=6とすれば、numlist[11×6]=66が呼び出される。
つまり、call-by-Name → 呼び出される瞬間の変数を参照する使い方となる。

擬似言語について基本的な構造はcall-by-textに似ているが、
局所変数j_renameを用いるかどうかが違う。
call-by-name → j_renameを使う
call-by-text → jをそのまま使う


[Call-by-Copy]
・実引数の参照を取得
・参照に格納されている値のコピーを仮引数に代入してcalleeを実行
・calleeから復帰時に仮引数の値を取得した実引数の参照の格納領域に代入
・仮引数の値が変更されると、対応する実引数に影響する

funcの関数を行う前に事前に、各引数のメモリ番地をコピーする。
funcの関数内では別々の変数として扱う。
func関数が終わったら、各引数の値を適切なメモリ番地に格納する


[Call-by-Text]
・実引数を評価せずに、式のまま仮引数に代入する
・仮引数に代入された式(実引数)は、calleeの環境で
定義されている変数はcalleeの環境を用いて、
それ以外はcallerの環境を用いて評価する
・意味としては、以下のマクロ展開をすることと同じ
・callee中で仮引数が出現する箇所を実引数で置き換える

プリプロセッサで擬似関数として動かした関数。
実際にはfunc関数の引数は存在しない。
つまり、main関数でi,j,kに関する各式を書いているに過ぎない。


evaluate=評価する

*thunkについて
1.《コ》サンク◆16ビットのメモリアドレスを32ビットに変換すること。
またはその逆。転じて別アーキテクチャのコードを読み出すこと。
16ビットと32ビットのプログラムではメモリアドレスの振り方が異なるので、
アドレスの変換をして呼び出す必要がある。

2.メモリアドレス(ポインタ)を返す(引数を持たない)関数 T *thunk()
なぜ “thunk” という名称なのかは諸説ある
ある式が実引数として関数に与えられるとき、
その式 の参照(つまりLHV)が必要な場合、その式を使った
thunkを定義しておき、それを呼び出すことで、その 式の参照が取得できる
int *n_thunk() { return &(s[i*j]); }
thunkを定義し、その関数へのポインタを受け渡すことができれば、
閉包に関係する情報をcalleeに与えることができる


[方針]
1、reference, name, value/referenceを順に適用
2、値が正しいか確認する。
3、適宜必要ならば修正する。

[refer to the lecture of PLT ]

2008-01-06

行列N×Nの90度左回転における最適化 ver 2






やっと終わった~。そして約10,000字。ってか最近10,000字越え多杉orz
高校の卒論がどれだけ糞だったか、分かった気がするわ。


さて、コレで残す課題はプログラミング言語論と数学Bとフーリエ解析の答え確認だけだぜ。

…って終わるわけがないがなorz


いや、でも出来るだけ終わらさなければな。

このままじゃ、課題と試験勉強のダブルブッキングで死亡フラグ立つわ。

目指すはA+。

[CPE optimization NOTE and exercise]

memo

[class11~12.pdf]
vector=<コ>一次元配列、ベクトル
persist=存続する、持続する、生き残る
sensitive=敏感に反応する
ocnventional=標準となった、オリジナリティのない、型にはまった
eventually=最終的には、結局のところは
volatile=揮発性(の)
retain=保持する、実行し続ける
generic=一般的な、総称の
retrieve=(情報を)検索する、読み出す、回収する、取ってくる
geometry=(関連ある部分同士の)配置、配列、(表面の)形状、幾何学
concentric=<数学>同心の、集中的な
platter=円盤状の記録媒体、大皿(に盛った料理)
aligned=位置合わせした
density=密度、濃さ、密集(度)、濃度
squeeze=圧搾する、締め付ける、強制する
attach=貼り付ける、添付する、加える
radially=半径方向に、放射状に
unison=調和、一致
approximate=
1.おおよその、概算の、近時の adj
2.接近する、に近づける、概算する
permute=~の順序を変える
Hierarchy=階層型組織、序列、優先度、順位
exhibit=展示する、発表する、(証拠を)提示する、(感情を)表に出す

[class14.pdf]
exploit=
1.セキュリティ上の弱点、突破口、バグを利用した裏技、手柄、功績
2.不当に使う、(性能を)十分に引き出す
dimension=寸法、面積、容量、次元、様子、様相

[Blog -Cache Memories-]
conflict=不一致、衝突、衝突する、抵触する、矛盾する
adjacent=近くの、隣接した、隣り合った、直前の
consecutive=連続した、継続的な、結果の、(論理の)一貫した
allocate=割り当てる、割り振る、配置する
fraction=分数、有理数、比、割合、端数、一部分
spatial=空間の

-hit time-
1 clock cycle for L1
3-8 clock cycles for L2
Miss Penalty Typically 25-100cycle



[instruction cache]別名:命令キャッシュ
マイクロプロセッサ内部に設けられた高速な記憶装置であるキャッシュメモリの一種で、
プログラムを一時的に保管する領域。

CPUは高速にアクセスできるキャッシュメモリに使用頻度の高いデータを
蓄積しておくことで低速なメインメモリへのアクセスを極力減らすよう設計されているが、
このうちプログラム(プロセッサへの命令群)を保存しておく装置のこと。

データを保存しておくデータキャッシュと異なり、
処理によって内容が更新されてメインメモリへそれを反映させるといった動作が
必要ないため、構造が単純化されている。

[firmware]
ハードウェアの基本的な制御を行なうために機器に組み込まれたソフトウェア。

機器に固定的に搭載され、あまり変更が加えられないことから、
ハードウェアとソフトウェアの中間的な存在としてファームウェアと呼ばれている。

パソコンや周辺機器、家電製品等に搭載されており、
機器に内蔵されたROMやフラッシュメモリに記憶されている。

パソコンのBIOSもファームウェアの一種である。
機能の追加や不具合の修正のため、後から変更できるようになっているものが多い。

2008-01-05

2次元配列とインクリメントの順序関係


初めて知った。自分的には大発見。 さっそくメモ。

C言語で
以下の5×5の2次元配列src,dstに対して、
[src]
0 3 3 2 9
0 8 2 6 6
9 1 1 3 5
8 3 0 6 9
2 7 7 2 8

[dst]
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

以下の動作を行うと
int a,b
a=0, b=0
dst[++a][++b] = src[++a][++b]; ※1
a=2, b=2
dst[a][b] = 0
dst[++a][++b] = src[++a][++b]; ※2
a=4, b=4
dst[a][b] = 0

※1→ dst[1][1] = src[2][2]となる 
同様にして
※2→ dst[3][3] = src[4][4]となる 

式は、左から右に評価していくので、
インクリメント順番も評価の順番に従って行われる

よって、dstの内容は
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 8 0
0 0 0 0 0
となる。

2008-01-04

行列N×Nの90度左回転における最適化





ん~、最適化の実験は、前回同様いつも思うような結果にはなってくれないな。

最近のCPUはほとんど中身がカオスで、実際に何がどう動作しているのか、
本職の人にもわからないらしいし、これはもう実験しまくるしかないないわww


しかし、初回の課題でドライバ作ってて良かった。。
ドライバ作成は一瞬で終了。頑張って作っててよかったわぁ。



最適化に関しては、とりあえずN×Nを分割して各々を90度回転させて、組み立てる関数は完成。

8×8~64×64あたりに分割すると、うまくどっかのキャッシュに乗るっぽい。

最適化のために他にやってみることは、

・変数をローカルフィールドに置く
・関数を解体して、直接書き込む
・gcc特有のオプションを使ってみる

とかかなぁ。とりあえず、このぐらいは最低限実験してみるか。

アセンブリコードは…まぁやってみたいけど、プログラミング言語論の課題が終わってからだな。


結局、冬休みはあってないようなものだったな。


以下メモ@Gcc optimization option (refer to "man gcc" in cygwin)

Options That Control Optimization

These options control various sorts of optimizations.


Without any optimization option, the compiler's goal is to reduce the cost of compilation and to make debugging produce the expected results.
*compilation=編集

Statements are independent: if you stop the program with a breakpoint between statements, you can then assign a new value to any variable or change the program counter to any other statement in the function and get exactly the results you would expect from the source code.
*assign=割り当てる、指定する

Turning on optimization flags makes the compiler attempt to improve the performance and/or code size at the expense of compilation time and possibly the ability to debug the program.
*expense=コスト(高)

The compiler performs optimization based on the knowledge it has of the program.

Using the -funit-at-a-time flag will allow the compiler to consider information gained from later functions in the file when compiling a function.

Compiling multiple files at once to a single output file (and using -funit-at-a-time) will allow the compiler to use information gained from all of the files when compiling each of them.
*multiple=複数の

Not all optimizations are controlled directly by a flag. Only optimizations that have a flag are listed.

-O
-O1 Optimize. Optimizing compilation takes somewhat more time, and a lot more memory for a large function.

With -O, the compiler tries to reduce code size and execution time, without performing any optimizations that take a great deal of compilation time.

-O turns on the following optimization flags: -fdefer-pop -fmerge-constants -fthread-jumps -floop-optimize -fif-conversion -fif-conversion2 -fdelayed-branch -fguess-branch-probability
-fcprop-registers

-O also turns on -fomit-frame-pointer on machines where doing so does not interfere with debugging.


-O2 Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff.
*tradeoff=見返り、交換(条件)

The compiler does not perform loop unrolling or function inlining when you specify -O2.
*in-line=一列に並んだ、直列(形)の , specify=指定する、明確にする

As compared to -O, this option increases both compilation time and the performance of the generated code.

-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags: -fforce-mem -foptimize-sibling-calls -fstrength-reduce -fcse-follow-jumps -fcse-skip-blocks -frerun-cse-after-loop -frerun-loop-opt -fgcse -fgcse-lm -fgcse-sm -fgcse-las -fdelete-null-pointer-checks -fexpensive-optimizations -fregmove -fschedule-insns -fschedule-insns2
-fsched-interblock -fsched-spec -fcaller-saves -fpeephole2 -freorder-blocks -freorder-functions -fstrict-aliasing -funit-at-a-time -falign-functions -falign-jumps -falign-loops -fsched-interblock -fsched-spec -fcaller-saves -fpeephole2 -freorder-blocks -freorder-functions -fstrict-aliasing
-funit-at-a-time -falign-functions -falign-jumps -falign-loops -falign-labels -fcrossjumping

Please note the warning under -fgcse about invoking -O2 on programs that use computed gotos.

-O3 Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -fweb and -frename-registers options.
*specified=指定の、規定の、特定の 、仕様が~の

-O0 Do not optimize. This is the default.

-Os Optimize for size. -Os enables all -O2 optimizations that do not typically increase code size. It also performs further optimizations designed to reduce code size.

-Os disables the following optimization flags: -falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -fprefetch-loop-arrays

If you use multiple -O options, with or without level numbers, the
last such option is the one that is effective.

通信時間の時間要素について

表6やっぱ間違ってた。これで、なんとか思惑通りの実験になったはず。

しかし、実験経過を無理矢理反映させようとしたから、
弱冠文章のロジックも無理矢理感があるような…

でも結果だけ書くのは虚しいしなぁ。

今後は、実験の順序見通しをしっかり立ててから実験に臨まないとな。

それと次からは、必要最低限の工数で最大限の効果を持たせるように意識しなくては。
時間もちょっとかかり過ぎてるし。

・目次
0. 動作環境
1. 実験内容
2. 実験結果
3. 考察
 3.1. Visual Route 8.0Jを用いた理論値の計測
 3.2. ドメインSearch(Whois)を用いた理論値の計測
 3.3. 各計測方法による理論値と実測値が違う理由
4. まとめ・感想
5. 参考資料

0. 動作環境
本実験に使用したコンピュータの動作環境は以下の通りである。次項から続く実験結果は、全て以下の環境下で計測した結果である。

動作環境:
OS: Windows XP Home Edition (5.1, Build2600) Service Pack 2
Processor: Genuine Intel(R) CPU T2300 @ 1.66GHz (2 CPUs)
Memory: 502MB RAM
通信形態:無線LAN
実験を行った場所:東京都北区赤羽
距離の計算方法:Google Earth


1. 実験内容
手順1.
各自のコンピュータから、できるだけ遠隔地にあると思われるコンピュータ 3台に対してpingコマンドを実行する。
その結果として表示されるMinimumの時間を、相手のコンピュータの名前と一緒に報告する。

手順2.
各自のコンピュータのIPアドレスを調べる。IPアドレスを調べるには各種の方法がある。
どのような方法を採ったか、その方法の説明と結果のIPアドレスを報告する。

手順3.
手順1で対象として選んだ相手方のコンピュータの1つを選ぶ。
自分のマシンと相手のコンピュータの間の距離を、何らかの方法で算出する。
この距離をシングルモードの光ファイバ中の光速(180km/ミリ秒)で割り、片道の通信時間の理論値を求めて報告する。

手順4.
手順3で算出した理論値と、手順1で求めた実測値は、通常は一致しない。この理由を考える。
実測値には理論計算で想定している他の時間要素が加わっている。この想定外の要素とは何か。これを考察して、各自の見解を報告する。


2. 実験結果
 今回の実験の計測に用いたドメイン名は、以下の通りである。
  ・web.mit.edu 米国マサチューセッツ州マサチューセッツ工科大学
  ・www.stanford.edu 米国カルフォルニオア州スタンフォード大学
  ・www.ox.ac.uk 英国オックスフォード州オックスフォード大学
上記のドメインに対し、pingコマンドを行った結果を添付資料data01_tables.xls表1に示した。
このときに使用したコンピュータのIPアドレスは”192.168.1.19”である。また、このIPアドレスはコマンドプロンプトのipconfigコマンドを用いて調べた結果である。

 次に、自宅から上記に示した各目的地までの直線距離と通信時間の理論値を表2に示した。
このとき、距離を求めるために用いた方法はGoogle Earthの距離計測機能である。
また、通信時間を求めるための通信速度には、シングルモードの光ファイバ中の光速(180km/msec)を適用した。

 表1と表2に示されている片道の通信時間を比較すると、実測値は理論値よりも2倍から3倍の時間がかかっていることがわかる。
さらに、直線距離だけを比較すると、Stanford, Oxford, MITの順に観測地から遠くなっていくが、通信時間はStanford, MIT, Oxfordという順になっていることがわかる。
これらのことから、通信時間は距離以外の時間要素を持っている可能性がある、ということが分かる。

3. 考察
 2.の実験結果から”通信時間は距離以外の時間要素を持っている可能性がある”ということが分かった。
しかし、2.の実験手順からだけでは「距離以外の時間要素が存在する」と断定するにはまだ早い、と考えた。

 なぜなら、この結果はGoogle Earthで直線距離を計測した理論値だからである。
実際のネットワークは直線上に繋がっているわけではなく、各国のネットワークセンターや、各ルータ経由しているはずである。
つまり、通信の距離は、単純な直線ではなく、各経由点を経由した折れ線になるはずである。
よって、距離を実際の値にさらに近づけるために、各経由点を把握する必要がある。
そして、そのためには別の観点から再度測定した方がよい、と考えた。

3.1. Visual Route 8.0Jを用いた理論値の計測
 各経由点を把握するためには、コマンドプロンプトのtracertコマンドを用いる必要がある。
しかし、今回は結果をグラフ化し、多くの整理された情報を簡易的に得るためにVisual Route 8.0Jというトレースソフトを用いて再度実測を行った。

 このVisual Route 8.0Jを用いて得た測定結果を、添付資料の2枚目のsheet ” Data pictures3.1~3.3”の図3.1, 3.2, 3.3に示す。
また、この図3.1, 3.2, 3.3の”位置”欄に注目して、各経由地を経由した距離をGoogle Earthで測り、得た結果が表4である。

 表4から、経由地を考慮した理論値と実測値を比較すると、各距離と通信時間の大小関係は一致した。
しかし、結果の理論値は実測値よりも1.5倍から2倍ほど大きい値となり、実測値とは大きく異なった結果となってしまった。
なんらかの未計算要素を踏まえても、理論値が実測値よりも大きいということはあまり考えられないので、この結果の計算方法に問題があると考えられる。


3.2.ドメインSearch(Whois)を用いた理論値の計測
 ここで、図3.1, 3.2, 3.3の”ms”欄と”位置”欄の相互関係を見ると、国を経由した割にはさほど通信時間がかかっていない部分が多く見受けられる。
このことから”位置”欄に書かれている国を必ずしも経由しているわけではないのかもしれない、と考えた。

 このことから、真の情報にさらに近づけるため、経由した各IPアドレスに対してWhoisサーチをかけ、直接自分でIPアドレスの持つ情報を調べてみた。Whoisのサーチにはhttp://www.gabura.com/のKIYO Project Web-Up-Serch/Gabura@Whois ver.0.1.4を使わせていただいた。
このWhoisサーチを用いて、各IPアドレスの持っている情報を調べ、各IPアドレスが使われている地理情報を調べた。その結果を表5.1, 5.2, 5.3に示す。

 表5.1, 5.2, 5.3を見ると、やはり必ずしも”位置”欄に書かれた国を経由していないことが分かる。
ここで、これらの表に書かれている各経由点をGoogle Earthで結んでいき、その距離を再度計算しなおした。その結果を表6に示した。

 表6に示されている往復通信時間の実測値と理論値を比較すると、各目的地までの理論値は実測値よりも下回っているので、
この計算方法にはまだ未計算の要素があると思われる。しかし、当初の直線距離で計算する方法よりは実測値に近い値を出すことが出来た。
また、距離と通信時間の順序関係も、実測した結果と同じ順序関係になっていることがわかる。


3.3. 各計測方法による理論値と実測値が違う理由
 3.2の実験結果から考えると、通信時間には距離以外の時間要素があると考えられる。その要素が何なのかについて考察をしていきたい。
図3.1, 3.2, 3.3の”ms”欄,”グラフ”欄, ”ホップ”欄に注目すると、グラフが大きな傾きを示す箇所はほとんどが国を越える瞬間であることが分かる。

 例えばOxfordの場合は、日本から一度アメリカを経由して、Sweden, London, Oxfordと繋がっているので、
大きな傾きが2箇所存在する。Stanfordも同様の傾きが見受けられる。

 一方で、図3.1MITの結果を見ると、アメリカのNTT America, Incを経由するまでの通信時間は、
StanfordやOxfordの場合とさほど変わらない値になっているが、その直後に大きな傾きが存在している。
StanfordとMITの距離だけを比較すると、NTT America, Incを経由してから各目的地までの距離に、さほど大きな差は無い。
つまり、MITへの通信には距離以外の大きな時間要素が働いている、と推察できる。

 また、経由点の数と通信時間は単調な正比例ではないことがわかる。いくつかの経由点では、次の経由点までにかかる通信時間よりも、
前の経由点までにかかる通信時間のほうが大きい箇所がある。また、この現象が起こる箇所は常に一定というわけではなく、
計測した時間帯によってその現象が起こる箇所は異なっていた。

 これらのことから、距離以外の時間要素として3つの要素があるのではないか、と私は考えた。

 一つ目の要素は、ネットワークのトラフィック状況である。
具体的に言えば、LANのCSMA/CDやトークンバッシング、TDMAなどの通信制御方式が起因しているということになる。
つまり、もしネットワーク上のある箇所に不特定多数のアクセスが重なっていれば、そこである種の通信制御が行われ、通信に何らかのロスタイムを被ることになる。

 二つ目の要素は、ルータの経路探索である。
3.2の実験では大まかな経由地を考慮して計測を行ったため、同Global IP アドレス範囲内の経由地は、全て一箇所の経由地として計算した。
これは、ISP事業者を通さないと細かい各経由地の情報が得られないためである。

 これにより、もし端折った各経由地を結ぶ線がジグザグな折れ線を示していた場合や、一度遠隔地を経由してから目的地に繋がる経路だった場合は、
さらに距離が加算されることになる。つまり、理論値の計算式には含まれていない通信時間が生じることになる。

 その典型的な例が図3.1の”ネットワーク”欄に書かれている”Performance Systems International PSINET-B2-54”の範囲である。
ここでは、いくつもの経由地を経由していて、ある箇所では約70msもの時間がかかってしまっている。
これは、ルータの経路探索以外の時間要素も含んでいると思われるが、3.2の実験の計算仮定には含まれていない何らかの時間要素であることには変わりは無い。

 三つ目の要素は、通信回線の種類である。
今回の実験では、通信回線は全て”光ファイバのシングルモード”という仮定のもと計算を行っている。
しかし、実際には他の回線を行っている箇所も多くあるはずである。

 また、光ファイバは各通信回線の中でほぼ最速に近い通信速度を持っているので、
他の回線を用いている通信箇所があった場合は、それは比較的通信時間のかかる通信回線になってしまうことが多い。
よって、光ファイバではない通信回線の箇所の分だけ、通信時間が余計にかかってしまう。

 以上のことから、通信時間には単純な距離以外にも、回線の混雑度や種類、また経由地を経由した回数も時間要素に含むことが出来ると考えられる。

4. まとめ・感想
 時間があればさらに深い実験を行いたかったが、他の課題との兼ね合いもあるので今回はここまでとした。
結果としては、まだまだ不明瞭な部分もあるが、今持っている知識ではとても包括しきれないネットワークの深さを知った。
ネットワーク関するさらなる深い知識を、これからも着実に身に着けていきたいと思った。

5. 参考資料
WHOIS IPドメインサーチ アドレス 検索 Gabura Inc
http://www.gabura.com/ip.html

ネクスト・イット株式会社 製品 Visual Route
http://www.next-it.com/product/vw/vr/index.html

2008-01-03

光ファイバシングルモードにおける距離と通信時間の関係(失敗)






距離と通信時間は関係あると思うけど、通信時間は他にも、
ルータを通った数やそのトラフィック状況にも依存するという罠。

いや、分かってはいたけど、もうちょっとそれらしい結果が出てほしかった。
実験のやり方ミスったのかなぁorz

まぁいいや。あとは考察するだけ。今日中に終わるはず。


【サーバー計画】
昨日はサーバーを色々イジイジしてたけど、CD-driveからのブートは出来るのに、
Harddriveからのブートが出来ない。というか、エラー以前に反応すらしていないという…


FedoraのLiveCDで起動させると通常に動くから、メモリ関係とマザーボードは大丈夫っぽい。が、FedoraでもcentOSでもHarddriveにインストールして、その後再起動すると反応しない…orz


もしや、Harddriveとマザーボードが繋がってない??


いくら安くても、Made in Chinaには手を出すべきではなかったのかもしれないな。
Serverでバグ頻発してたら、流石に時間の無駄だわ。
とりあえずIBMにサポート要請しなくては。

2008-01-01

Background ver.001




-------------------------------
Index
・今
・学部時代にやってきたこと
・身を置いている所
・目標
・成果
・告知
・その他
-------------------------------



【今】
平日:某会社のsolution部門で新技術の調査・開発。
週末:予備校でTOEFLのR/LとWritingの勉強 + そこそこ重いassignments / week。
結論:死亡フラグ。


【学部時代にやってきたこと】
『Berlitz pronounciationの修了』
得たモノ:何度発音のテストをしても講師には"Almost"と言われ続けることに対する忍耐力。
分かったこと:素直にアメリカ語学留学しとけばよかったorz。一人でひたすら勉強するのは自分の性に合わないらしい。

『早大山岳アルコウ会HP & データベース"WAK DB"の作成』
joomlaとDBQで作りました。CMSだと制作が楽だわぁ。2008年4月現在、β版のため、正式な運用には至っていないけど、1,2年後には立派なDBになっていて欲しいな。
http://www.arukou.sakura.ne.jp/

WAK database(仮)
http://www.arukou.sakura.ne.jp/component/option,com_dbquery/Itemid,28/

『アジア大学ビジネスアイデアコンテスト』
2007年3月に北京大学で行なわれた
"2007 KT&G Asian Students' Venture Forum
-Business Idea Contest-"に第3位入賞。チームメンバーは当時全員1年生。何故かみんな怒Sか度Mな人だった。そんな両極端な6人で結成されたチームの成果。みんな凄い奴らだ。同期だし、俺も負けてらんないわ。あと、シンガポール人は頭良すぎ!
http://asiansvf.com/

『第1回 日韓学生未来会議 企画・運営・指揮』
2007年2月の大企画。途中から組織に加わったんだけど、なんか気付いたら色々やってました。人生初の大企画&運営でした。今は他の事をやっていて、あまり顔を出せないけど、今の自分が積極的に行動できるのは、この会議をやり通したからなんだろうな、と思う。後輩達が受け継いで繋いでいく第2回以降の会議にwktk。
http://www.jkc-future.net/jksff/

『フランス語学留学』
2007年2月からフランスでフランス語勉強してました。フランス蝶最高!でもフライト時間長すぎだよワトソン君!今でもフランス語は大好きだし、もっと使えるようになりたいけど、最近は英語に若干浮気気味だったり。とりあえず、パリ近郊はお腹いっぱいだから南仏に行ってみたい!

『Internship -擬似プロジェクト-』
2007年9月に大阪まで行ってシステム開発の擬似プロジェクトに挑戦した。擬似プロジェクトでは、2年生のくせに何故か3,4年生のメンバー率いて頑張っとりました。最後まで自分のことを3年生だと思ってた人は数知れず。年齢詐称乙。しかし、結果は惨敗。工程管理とスケジュール管理でヘマを犯しました。おかげでシステム設計書とマニュアルが納品できなかった。すごく・・・悔しいです・・・。ただ、学んだことは多かった。ああ、あと、SIerでは働きたくないな、と思いました。

『南アルプス縦走』
2007年8月、頼れるメンバーと南アルプスの上から下まで長期縦走しました。でも2006年8月も南アルプスを上から下まで長期縦走してたから、実は今回で2回目。ただし、今回はスタート地点が北岳→仙丈ケ岳に、ゴール地点が椹島→畑薙ダムにグレードアップしており、距離と山中拍数が結構伸びてます。結果的には、泊数は12泊13日ぐらいだったかな(多分)。予備日も使う予定だったんだけど、メンバーの体力が皆キモ過ぎるレベルで結局一日も停滞しなかった。あ〜、でも最近は山に登ってないな。おかげさまでメトボリックなお腹と化しました。


【身を置いてる所】
日韓「JKSFF」執行部広報OB
山岳「早大山岳アルコウ会」
BC「ドリーマーズ」
FC「FCアトレティコ・ラッセーラ」創設者&幹事
地域「地域スポネット『すぱんく』」スタッフ
BC「『すぱんく』スポーツ開放」管理人代理
BC「clubジョーダイ君」
英語サークル「WRESS」


【でっかい目標】
Googleインターン選考に合格。そして、ゆくゆくはNEETへ昇華。


【最近の大目標】
・TOEFL ibt 80点以上。
・インターン先からreferenceを貰えるだけの功績を残すこと。


【他最近の目標】
・英語で不自由なくdiscussion出来る
・回路理論の単位回収orz
・GPAをもっと高くする


【最近の成果】
・サーバ構築が出来たような気がする。
・(この年になってようやく)WindowsからLinuxへの移行。
・基本情報技術者合格
・WAK データベース完成
・Berlitz pronouciation修了

----- 以下、壮大な蛇足 -----

【告知1】
現在FC『アトレティコ・ラッセーラ』の代表やっとります。入部からマッチメイク、宣伝・告知等など興味がありましたらお気軽にお尋ね下さい。
HP→http://www.geocities.jp/atletico_l/
Mixi→http://mixi.jp/view_community.pl?id=1946980
SNS→http://soccersns.jp/team/1884/


【告知2】
『北区立赤羽中学校体育館バスケット開放参加者募集』
現在、東京都北区立赤羽中学校体育館の夜間バスケット開放を行っております。で、僕がその管理人だったりします。

興味のある方はコチラ↓。
質問等は僕に直接メッセージでも可。

「赤羽中学校バスケットボール開放」
http://mixi.jp/view_community.pl?id=1947170


【告知3】
『地域スポネット「すぱんく」の参加者募集』
僕の地元である東京都北区には「すぱんく」という地域スポーツネットワークの団体があります。「すぱんく」では学校や公立の施設を利用して、住民の皆様に文化的な活動や健康的なスポーツ活動を楽しんでいただく「場」を提供しています。

現在はサッカー、フットサル、バスケットボール、バトミントン、卓球、ダンスなどの種目を取り扱っているので、興味のある方、体を動かしてみたいと思っている方、是非お気軽にお尋ねください。

公式web→http://www.web-spank.com/
Mixi→http://mixi.jp/view_community.pl?id=1942881



【趣味】
自分が聴いてる曲の紹介とか音楽観とか色々書いてあります。まぁどんな曲を聴いてるかってのは参加してるコミュニティ見てくれても分かうわ何するんだやm…

あと、音ゲー全般(特にドラムマニア)が得意だったりします。


【生息地】
『Cafe Miyama』
十中八九来ればいます。教科書やらPCやらプリントやら色んなものを散らかして勉強してます。そんな明らかに邪魔でしかない僕にも優しいMiyamaの店員には、きっとインテルはいってるに違いない。


【注意】
ログイン時間が『5分以内』になっていることが多いと思いますが、それは暇なんじゃなくて忙しい最中でもMixiを見るという心の余裕を常に持たせて、自分n(ry


【思考回路】
好奇心>>>>>(越えられない壁)>>>>>羞恥心


【座右の銘】
(゚Д゚ ):. _ かけてよし!
r'⌒と、j   ヽ
ノ ,.ィ'  `ヽ. /
/       i!./
(_,.         //
く.,_`^''ー-、_,,..ノ/


/(*゚Д゚) かぶってよし!
/ :::У~ヽ
(__ノ、__)


'⌒⌒'⌒ヽ  まるまってよし!
(゚Д゚* ),__)


( ゚∀゚ ):. _ お布団サイコー!!
r'⌒と、j   ヽ
ノ ,.ィ'  `ヽ. /
/       i!./
(_,.         //
く.,_`^''ー-、_,,..ノ/



どうみてもモフモフです。
本当にありがとうございました。