kivantium活動日記

プログラムを使っていろいろやります

画像処理で大腸菌のコロニー数を数えたかった話 その2

kivantium.hateblo.jp
の続編です。

前回は先行研究を一切調べずに適当にやったので今回は少し先行研究調査をして前回よりはまともな方法を実装したいと思います。

先行研究

Google検索したところ

ということが分かりました。

見た論文の中で一番簡単そうだったCell counting based on local intensity maxima grouping for in-situ microscopy - IEEE Xplore Documentを実装することにしました。

論文の内容と妥協ポイント

この論文では

  • Cell cluster Region Segmentation
  • Local Intensity Maxima Detection
  • Local Intensity Maxima Grouping
  • Cell Counting

の4段階で細胞数をカウントしていました。

Cell cluster Region SegmentationではMartinezの方法で細胞領域のセグメンテーションを行うと書いてあったのですが、Martinezの論文が入手できませんでした。そこでそれっぽいセグメンテーションができる閾値を手動で設定することにしました(妥協ポイント1)

Local Intensity Maxima Detectionではbilateral filterを掛けた後、各ピクセルについてそのピクセルを中心とする3x3の領域で最も明るい場合にlocal intensity maximumと判定するという処理をしていました。実験の結果3x3では小さすぎるようだったのでwindow sizeも手動で設定することにしました(妥協ポイント2)

Local Intensity Maxima Groupingではlocal intensity maximumを5つの基準に従ってグルーピングしていました。しかし、論文の基準は「2つのmaximumを結ぶ直線が細胞の境界と交差しない」のような実装が面倒なものが多かったので、2つのmaximumが同じwindowに入るならグループにするという単純な基準を採用しました(妥協ポイント3)

Cell Countingはグループの数を数える処理です。

実装

以上の妥協を行った実装が以下のようになります。(何も見直ししてないからコードが汚い)

#include <opencv2/core.hpp>
#include <opencv2/imgproc.hpp>
#include <opencv2/imgcodecs.hpp>
#include <opencv2/highgui.hpp>

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>

cv::Mat org, src, bin, blured, dst;
int wsize = 5;
int threshold = 200;

using P = std::pair<int, int>;

struct UnionFind {
    std::vector<int> par;
    UnionFind(int n) : par(n, -1) {}
    int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (par[y] < par[x]) std::swap(x, y);
        if (par[x] == par[y]) --par[x];
        par[y] = x;
    }
};

void drawWindow(void) {
    cv::Mat img = org.clone();
    cv::bilateralFilter(src, blured, 7, 5, 35);
    cv::threshold(blured, bin, threshold, 255, cv::THRESH_BINARY);
    std::vector<P> cell;
    for(int y=wsize; y<blured.cols-wsize; ++y) {
        for(int x=wsize; x<blured.rows-wsize; ++x) {
            int c = blured.data[y*blured.step+x]; 
            bool is_max = true;
            for(int dy=-wsize; dy<=wsize; ++dy) {
                for(int dx=-wsize; dx<=wsize; ++dx) {
                   if(blured.data[(y+dy)*blured.step+(x+dx)] > c) is_max = false;
                }
            }
            if(is_max && bin.data[y*bin.step+x] == 255) {
                int p = y*img.step+x*img.elemSize();
                img.data[p+0] = 0;
                img.data[p+1] = 0;
                img.data[p+2] = 255;
                cell.push_back(P(y, x));
            }
        }
    }

    UnionFind uf(cell.size());
    for(size_t i=0; i<cell.size(); ++i) {
        for(size_t j=0; j<cell.size(); ++j) {
            if(abs(cell[i].first - cell[j].first) < wsize && abs(cell[i].second - cell[j].second) < wsize) {
                uf.unite(i, j);
            }
        }
    }

    int pop = 0;
    for(size_t i=0; i<cell.size(); ++i) {
        if(uf.find(i) == i) pop++;
    }
    std::cout << "population is: " << pop << std::endl;

    cv::imshow("Source", img);
    cv::imshow("Binary", bin);

}

// トラックバーに変化があった時に呼ばれる関数
void on_trackbar( int, void* ) {
    drawWindow();
}

int main(int argc, const char** argv) {
    org = cv::imread(argv[1]);
    src = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
    dst = cv::Mat(src.size(), CV_8UC3);

    // 画像の読み込みに失敗したらエラー終了する
    if(src.empty()) {
        std::cerr << "Failed to open image file." << std::endl;
        return -1; 
    }

    // トラックバー付きウィンドウの作成
    cv::namedWindow("Binary");
    cv::createTrackbar("threshold", "Binary", &threshold, 255, on_trackbar);
    cv::createTrackbar("window size", "Binary", &wsize, 15, on_trackbar);
    drawWindow();

    while(true) {
        int key = cv::waitKey(0);
        if (key == 'q') {
            return 0;
        }
        if(key == 's') {
            cv::imwrite("result.png", dst);
        }
    }
}

実行結果

入力画像
f:id:kivantium:20170508230735p:plain

手動で閾値を設定してセグメンテーションした結果
f:id:kivantium:20170508230637p:plain

local intensity maximumとなるピクセルを赤く表示した結果
f:id:kivantium:20170508230819p:plain

出力は

population is: 21

でした。

もう少し難しい入力画像と処理結果
f:id:kivantium:20170508230907p:plain
f:id:kivantium:20170508231003p:plain
f:id:kivantium:20170508231012p:plain

population is: 55

これより大きい画像について実行しようとすると、画像の場所ごとに明るさが違うようで単純な閾値設定による二値化ではうまくセグメンテーションができませんでした。AdaptiveThresholdも試しましたが、OpenCVの関数ではうまくできませんでした。次回は妥協ポイントその1をなんとかする必要がありそうです。

RNNによるツイートの自動生成

授業で「Deep Learningを使って何か作る」という課題を与えられました。チーム開発なのですが、知らないうちにテーマがツイートの自動生成に決まっていたので実装をやりました。発表内容は以下のスライドを見てください。

以下、実装の詳細を説明します。
使ったコードはkivantium/rnn-twitter · GitHubに置いてあります。
github.com

char-rnn (Keras)

char-rnnはKarpathyがThe Unreasonable Effectiveness of Recurrent Neural Networksで紹介したことで有名になり、各種フレームワークに移植されているLSTMの有名なモデルです。モデルの説明はKarpathyの記事を読んでください。
Kerasを使いたかったのでkeras/lstm_text_generation.py at master · fchollet/keras · GitHubを元に実装しました。

かな漢字混じりの文章をそのまま学習させたところ意味のある文章が生成されなかったので、入力文字列を全てカタカナにする前処理を行いました。

漢字の読みを取り出す (Mecab, Python)

MeCabの辞書としてmecab-ipadic-neologdを使いました。(過去記事

Pythonバインディングsudo apt-get install python-mecabで入ります。

MeCab形態素解析を行うと読み情報が得られるので以下のようなコードで取り出します。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import MeCab
 
mt = MeCab.Tagger("-Ochasen -d /usr/lib/mecab/dic/mecab-ipadic-neologd")
mt.parse('')
text = 'あらゆる現実をすべて自分のほうへねじ曲げたのだ。'
node = mt.parseToNode(text)
node = node.next
data = ''
while node:
    if node.next:
        data += node.feature.split(',')[-2]
    node = node.next
print data

結果は

アラユルゲンジツヲスベテジブンノホウヘネジマゲタノダ。

となります。

辞書に読みが入っていないと*になるので気になる人は手動で取り除いてください。
Pythonエンコーディングは厳しいのでうまくいかなかったら頑張ります。

Yahooのかな漢字変換APIを使う (Python)

かな漢字変換を自分で実装するのはつらいのでYahooのAPIを使いました。
テキスト解析:かな漢字変換 - Yahoo!デベロッパーネットワーク

利用するにはアプリケーションIDが必要なのでご利用ガイド - Yahoo!デベロッパーネットワークに従って取得します。

カタカナからひらがなの変換はjaconvを使いました。GitHub - ikegami-yukino/jaconv: Pure-Python Japanese character interconverter for Hiragana, Katakana, Hankaku and Zenkaku
また、XMLの解析にはBeautifulSoupを使いました。Beautiful Soup Documentation — Beautiful Soup 4.4.0 documentation
どちらもpipで入ります。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import jaconv
import requests
from bs4 import BeautifulSoup

text = u'アラユルゲンジツヲスベテジブンノホウヘネジマゲタノダ。'

hira = jaconv.kata2hira(text)
yahoo_url = "http://jlp.yahooapis.jp/JIMService/V1/conversion"

appid = 'PUT YOUR ID HERE'

parameter = {'appid': appid,
            'sentence': hira,
            'results': 1}
r = requests.get(yahoo_url, params=parameter)
soup = BeautifulSoup(r.text)
sentence = ''
for word in soup.find_all('candidatelist'):
    sentence += word.find('candidate').text
print(sentence)

出力は

あらゆる現実をすべて自分の方へねじ曲げたのだ。

となります。
ここまでの機能で適当な文章が作れます。
データセットとしてはYJ Captions 26k Datasetの説明文を抜き出して使いました。

文章を作るだけではbotとしての面白みに欠けるので画像を生成しようと思いました。
運の良いことにMS COCOの説明文からGANで画像を生成する研究があり、コードと学習済みデータが公開されているのでそれを使おうと思いました。
GitHub - reedscot/icml2016: Generative Adversarial Text-to-Image Synthesis

しかし、この研究は英語から画像を生成しているので生成した日本語から英語にする必要があります。

Microsoftの翻訳APIを使う (Python?)

Google翻訳APIは有料だったのでMicrosoftAPIを使います。
使い方についてはたくさんの解説記事がありますが、最近仕様が変わったらしくほとんどの記事は今では使えない方法でした。
見つかった中で唯一動いた自動要約&ニューラルネット翻訳で海外の記事を読みやすくするSlackBot - Qiitaに従いました。

Cognitive Services - Text Translationに従ってkeyを取得します。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import subprocess
from bs4 import BeautifulSoup

def popen(cmd):
    outputs = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    stdout, stderr = outputs.communicate()
    return stdout

text = 'あらゆる現実をすべて自分の方へねじ曲げたのだ。'

token_url = "https://api.cognitive.microsoft.com/sts/v1.0/issueToken"
translate_url = "https://api.microsofttranslator.com/v2/http.svc/Translate"

KEY = 'YOUR KEY HERE'

CATEGORY = "generalnn"
request_token = popen('curl -X POST \"{url}\" -H \"Content-type: application/json\" -H \"Content-length: 0\" -H \"Accept: application/jwt\" -H \"Ocp-Apim-Subscription-Key:{key}\"'.format(url=token_url, key=KEY))
result = popen(
    "curl -X GET --header \'Accept: application/xml\' \'{url}?appid=Bearer%20{token}&text={text}&from=ja&to=en&category={category}\'".format(
        url=translate_url, token=request_token, text=text, category=CATEGORY))
soup = BeautifulSoup(result)
print(soup.string)

出力は

All the realities were screwed towards myself.

となります。

さすがにこの方法は汚い気がしますがDone is better than perfectと唱えて次に進みます。

GANによる画像の生成 (Torch, AWS)

GitHub - reedscot/icml2016: Generative Adversarial Text-to-Image SynthesisAWSで動かしました。

  • READMEのリンクからCOCO caption data in Torch formatCOCO GAN-CLSをダウンロード
  • CONFIGのファイルの位置を書き換える
  • scripts/coco_queries.txtに画像を生成したい英文を入れる
  • ./scripts/demo_coco.shを実行して画像を生成する

うまくいくと
f:id:kivantium:20170121141048p:plain
みたいな画像が出来ます。

こうして得た日本語文と、対応する画像をれんと (@licarent) | Twitterに流しています。

うまくいった例を貼り付けておきます。



RNNが生成する日本語文はいまいちで、GANが生成する画像はさらにいまいちなのですが、今の僕の技術レベルだとこれくらいが限界でした。
もっと面白いbotを作りたいものです。

AWSのGPUで機械学習した話(Torch編)

TL; DR

AWSは初期状態でGPUインスタンスを立てられない設定になっていることがあるから気をつけましょう


学校で「ディープラーニングを使って何かを作れ」という課題が出たのでGenerative Adversarial Text-to-Image Synthesisを動かそうと思ったのですが、どうやらこれはGPUがないと動かないコードのようで手元で動きませんでした。
締め切りも近く自分で学習させている暇はないのでAWSを借りることにしました。

AWSAmazonが運営しているサーバーサービスで、Amazonの全営業利益の半分以上を稼いでいるそうです。

Deep Learning AMIを使う

時間課金されるAWSで環境構築してる暇はないので、既に環境構築されている環境がないかなと思って調べたらBitfusion Boost Ubuntu 14 Torch 7という環境構築済みのイメージがあったので使うことにしました。値段は$0.066/hrなので環境構築にハマる時間を考えたら十分元が取れそうです。

GPUが使えるインスタンスはP2とG2があり、一番安いg2.2xlargeを使うことにしました。値段は変動するそうなのですが、使ったときは$0.65/hrだったので1日くらいならあまり負担になりません。

まずは、クラウドでの Linux 仮想マシンの起動方法 – AWSチュートリアルに沿って無料枠のサーバーでSSHの仕方などを学びました。

次に、Documentation: Machine Images - Bitfusion.ioに従ってDeep Learning用のインスタンスをセットアップしましたが、ここで問題が起きました。
ドキュメントの画像によると
http://www.bitfusion.io/wp-content/uploads/2016/11/2-8-768x497.png
でLaunch with 1-clickを押せばインスタンスが起動するはずなのに何分待っても起動が確認できませんでした。
起動していなければいいのですが、起動の確認方法を知らないだけで料金が発生しているかもしれないと思うと怖くなり一旦アカウントを削除しました。

翌日、AWS GPUインスタンスを利用して高速な機械学習環境を手に入れよう | Tech-Sketchに従って動かしてみたところ

You have requested more instances (1) than your current instance limit of 0 allows for the specified instance type. Please visit http://aws.amazon.com/contact-us/ec2-request to request an adjustment to this limit.

というエラーが発生しました。どうやら新しいアカウントではGPUインスタンスの数に制限があるようです(DashboardのLimitsから確認できます)

LimitsページのRequest limit increaseから「g2.2xlargeの制限を増やしてくれ〜」と申請したところ1日半くらいでメールが届いて使えるようになりました。

この状態でBitfusionのAMIでg2.2xlargeを立てたところTorchの環境は完璧に整備されている上にgitなども揃っていて、必要なデータを転送するだけで目的のコードを動かすことが出来ました。Bitfusionは他にもTensorFlowやChainerなどの環境構築済みのAMIを売っているようなので必要があったら使ってみようと思います。
AWS Marketplace: Bitfusion.io

以上をまとめると、

  • Launch with 1-clickボタンはエラーが出なくて怖い
  • 環境構築済みAMIは便利、金で時間を買おう

ということになります。

何を作ったかは明日の発表会が終わったら記事にします。
twitter.com

2016年に読んだ本

2016年最後の日なので今年読んだ本を振り返ってみたいと思います。

まんがタイムKRコミックス

今年もたくさんのきららコミックスを読みました。

NEW GAME!

今年発売された4巻のコンペの話や5巻の進路に悩む話など、挫折しながらも前に進んでいく青葉ちゃんの姿がとてもとてもよかった。

きんいろモザイク

忍たちも高校三年生になり修学旅行の話が中心でした。言うまでもなくよかった。

がっこうぐらし!

学生控室に置いてあったので読んだ。アニメに比べると原作は緊張感が漂っていてすごく好きです。大学編から出てくる喜来比嘉子ちゃんが好き。

まちカドまぞく

まちカドまぞく (2) (まんがタイムKRコミックス)

まちカドまぞく (2) (まんがタイムKRコミックス)

魔族の力に目覚めた主人公が魔法少女をぶっ倒して世界を支配する作品のはずですが、そこはきららコミックスなのでゆるい感じになっていきます。
だんだん話が広がってきていて今後に注目です。

すわっぷ⇔すわっぷ

すわっぷ⇔すわっぷ (2) (まんがタイムKRコミックス)

すわっぷ⇔すわっぷ (2) (まんがタイムKRコミックス)

キスをすると入れ替わる主人公たちが入れ替わりを使って日常を少し便利にすごしていきます。2巻になっても相変わらず入れ替わって楽しいねという感じでもう少し話が広がってほしいなと思います。

双角カンケイ

こちらは双子が入れ替わっていたら(女の子から)告白されてしまい、ばれないようにハラハラドキドキの生活が続くという話です。2巻完結でそろそろ2巻が出るそうなので楽しみにしています。

スロウスタート

おたふくかぜで高校受験ができず周りと一年遅れで高校に入った主人公の話。みんないい人で優しい世界です。「お外にも出たくない」「ひきこもりになるの」はこの1巻の一コマ。

ご注文はうさぎですか?

絵のかわいさも話の面白さもどんどん上がっていて本当にすごいなぁと感じます。

ステラのまほう

ステラのまほう 1巻 (まんがタイムKRコミックス)

ステラのまほう 1巻 (まんがタイムKRコミックス)

アニメ化されると聞いて買い揃えましたがあまりピンと来ませんでした……

きらりブックス迷走中!

きらりブックス迷走中!  (1) (まんがタイムKRコミックス)

きらりブックス迷走中! (1) (まんがタイムKRコミックス)

書店で働く常識のないお嬢さまの話です。きららMAX掲載作品の中できんモザの次に推しています。きららコミックスについてのブラックな発言が好きです。
発売日に作者が書店に来るイベントがあったので行ってきました。

ペンにまします神サマの

これもきららMAX掲載作品です。漫画のキャラクターが実体化するペンを手に入れてしまった結果起こるドタバタコメディのはずだったのですが、だんだん方向性が分からなくなってきました……

その他の漫画

まほろまてぃっく

botの名前をまほろにしているにも関わらず読んでいませんでした。家にやってきたアンドロイドのメイドのまほろさんと過ごす前半の日常パートも、「管理者」との戦いが激化する後半のシリアスな話も面白くて非常によかったです。ニコ生の一挙も見ました。

となりのロボット

となりのロボット

となりのロボット

ロボットと人間の百合というジャンルが成立するのかと驚かされた作品。よかった。

アフターアワーズ

これも百合系の話。クラブでの音楽みたいな世界と縁がなかったのでそういう世界もあるのだなと新鮮に感じた。

バーナード嬢曰く。

本好きあるある(?)を書いたギャグマンガ。アニメがよかったのでまだ一巻だけですが読んでいます。SFが好きな割にそんなに読んでないので神林のオススメを読んでいこうかなと思います。

カガクチョップ

カガクチョップ(1) (メテオCOMICS)

カガクチョップ(1) (メテオCOMICS)

科学部の頭おかしい発明で起こるドタバタを書いた作品。キルミーベイベーの人が描いてる。

最終兵器彼女

「こんなこと言ってごめんね、でも本当です。」の元ネタということで読んだ。世界が滅んでも僕達が愛しあっていればいいやみたいな話は好きではないのであまり気に入らなかった

ガールズ&パンツァー リボンの武者

タンカスロンというもう一つの戦車道を描いた作品。熱い戦闘描写や、他校から見た大洗女子の扱いなど極端な書き方が非常に面白い。

ダンジョン飯

ダンジョンのモンスターを料理して食べていくという話。毎回アイデアがすごい。

ライトノベル

この素晴らしい世界に爆焔を!

2016年ベストヒロイン(kivantium調べ)ことめぐみんが冒険に出て本編に登場するまでの物語。一巻で爆裂魔法を初めて撃つシーンは涙なしには読めない。

WORLD END ECONOMiCA

株取引で天下を取ろうという話。「羽月莉音の帝国」と比べるとドキドキが足りないし展開もいまいちだった。

小説

精霊の箱

「白と黒のとびら」の続編で、チューリングマシンに関する様々なテーマを下敷きにした物語が展開される。「これは停止性問題の話だから結末はこうだろう」などと分かるのに最後まで飽きさせずに物語が展開されていて本当にすごい。このような本が存在できることに驚きを感じる。

最短経路の本

最短経路の本 レナのふしぎな数学の旅

最短経路の本 レナのふしぎな数学の旅

競技プログラミングの強い人がアルゴリズムの面白さに目覚めたきっかけと言っていたから読んだ。こちらはアルゴリズムを対話的に説明しているだけで物語性も薄く、「精霊の箱」がいかにすごいかを感じるだけになってしまった。

ハケンアニメ!

ハケンアニメ!

ハケンアニメ!

覇権アニメを作るべく奮闘する監督やアニメーターたちの話。これはこれで面白いのだがSHIROBAKOと比べてしまうと少し霞む。

1984年

一九八四年[新訳版] (ハヤカワepi文庫)

一九八四年[新訳版] (ハヤカワepi文庫)

ディストピアものの代表として名高い作品。この本が後世の作品に影響を与えているため仕方がないことなのだが、新鮮さがなくて退屈に感じてしまった。

脳・人工知能に関する本

メカ屋のための脳科学入門-脳をリバースエンジニアリングする-

工学部の人向けの脳の講義をまとめた本。あまりリバースエンジニアリングしてる感じはなかったが脳に関する有名な実験が一通りまとまっていて脳について知るとっかかりとしてよかった。

コンピューターで「脳」がつくれるか

コンピューターで「脳」がつくれるか

コンピューターで「脳」がつくれるか

kazoo氏の書いた人工知能本。入門書としてはよさそう。

脳の計算論

脳の計算論(シリーズ脳科学 1)

脳の計算論(シリーズ脳科学 1)

脳の数理的側面についての本。モデル作ってみたけどよく分からんという感じの内容で、読んでも特に脳のことはよく分からなかった。

脳・心・人工知能 数理で脳を解き明かす

甘利さんの書いた脳の本。数理で脳を解き明かすためにいろいろ頑張りましたよと書いてあるがブルーバックスなので説明が甘く詳細は分からなかった。

昆虫―驚異の微小脳

昆虫―驚異の微小脳 (中公新書)

昆虫―驚異の微小脳 (中公新書)

昆虫は小さい脳でいろいろすごいことをやっていると説明した本。一応数理モデルでの説明があるが不十分に感じた。

考える脳 考えるコンピューター

考える脳 考えるコンピューター

考える脳 考えるコンピューター

人工知能ベンチャーをやっている人が書いた人工知能の本。全然裏付けがないポエムという感じだったが、この本にあった発生段階に神経を繋ぎ変えてもその部位が正しく反応できるように成長できるから脳は部位にかかわらず汎用的なアルゴリズムで学習しているのではないかという仮説は面白かった。

生物化するコンピュータ

生物化するコンピュータ

生物化するコンピュータ

計算への生物的アプローチをしている学者数人の研究について書いた本。こんなトピックがあるんだなぁと眺めるくらいしかできない掘り下げ方だった。

脳についての本はいろいろ読んだが、表面的なところは分かるが実際何をやっているかは何も分かってないという感じの本ばかりで脳研究の難しさを感じた。
はやく脳のことがわかるようになりたい。

組織論っぽい本

人月の神話

人月の神話【新装版】

人月の神話【新装版】

名作としてよく挙げられる本なので読んでみた。人月という単位は役にたたない程度の話しかないかと思っていたら、組織はどうやって作るべきかなどの話に踏み込まれていて非常に面白かった。Qiitaなどのポエム記事で見かける失敗事例はだいたいこの本に既に書かれていることで、古典的名作はすごいし名作と言われる本はちゃんと読んでおこうという気持ちが強くなった。
ピープルウエア 第3版
ピープルウエア 第3版

ピープルウエア 第3版

人月の神話で紹介されていたから読んだ。生産性の高い組織をどうやって作るかという話。オフィスに壁をつくって静かな空間で作業しようなど本当にその通りだという主張ばかりだったのだけど、ビルはこうやって建てようだとか、アパートを貸しきって開発場所にするほうがずっといいみたいな一社員ではどうしようもない話が多かった。

ライト、ついてますか

ライト、ついてますか―問題発見の人間学

ライト、ついてますか―問題発見の人間学

これも人月の神話関係で読んだ。問題を解く前に本当に問題が妥当かと考えてみたら良い解決策について思い浮かぶという話。(この結論だけ知っておけば読まなくてもいいと思う)
ライト、ついてますか?」の話は面白かったので書いておく。

道路のトンネルを抜けた直後にある展望台で、トンネルに入るときにつけたヘッドライトを消さずに駐車してしまってバッテリー上がりになる人が多発した。
この問題を解決するにはトンネルの出口に「ライトを消せ」という標識を立てることが考えられるが、そうすると夜でもライトを消してしまう人が出るかもしれない。
かといって「昼ならライトを消せ、夜ならつけたままにしろ」という看板は長くて読めない。さてどういう看板を立てるか?

答え: 「ライト、ついてますか?」と一言聞く看板を立てればドライバーが適切な判断をするはずである

失敗の本質

失敗の本質―日本軍の組織論的研究 (中公文庫)

失敗の本質―日本軍の組織論的研究 (中公文庫)

日本軍の敗戦の原因を分析した本。日本的組織の悪いところとして最近言われることが全部書かれていて古典的名作の力を感じた。(読んだあとのまとめメモ

イノベーションのジレンマ

イノベーションのジレンマ―技術革新が巨大企業を滅ぼすとき (Harvard business school press)

イノベーションのジレンマ―技術革新が巨大企業を滅ぼすとき (Harvard business school press)

これは去年読んだ本だが、「失敗の本質」と同じように大企業が環境適応能力を失ってベンチャー企業に敗れていく様子が説明されていて非常に印象的だった。

シリコンバレー 最強の仕組み

シリコンバレーがなぜすごいかに関する本。人が集まって起業家文化があるからという話で目新しい話はあまりなかった。

経済学っぽい本

ウォール街のランダム・ウォーカー〈原著第11版〉

9版を読んだ。株価の動きは予想できず、分かるのは全体として成長していく傾向にあることだけだからインデックス投資をしろと説いた本。
この本を読んでから機械学習で投資の研究をする気が失せたので今年一番影響を受けた本かもしれない。
この本に従って日経平均連動ETFを買っても儲からず、トランプ相場にも乗れなかったのでもう株取引はやめた。

セイラー教授の行動経済学入門

セイラー教授の行動経済学入門

セイラー教授の行動経済学入門

伝統的な経済学は各人が合理的な行動をすることを前提にしているが、実際には不合理な行動がたくさん確認されるということを説いた本。
確かにその通りなのだが、人間の心理などを組み込んだモデルをどう構築して検証できるかということは分からず、経済学分からんという気持ちが強くなった。

ヤバい経済学

ヤバい経済学 [増補改訂版]

ヤバい経済学 [増補改訂版]

常識のように思われていることもデータを見ると実はそうでもないかもしれないという事例を検証した本。
この本で常識の代替仮説として提唱されていることも同じように反証するデータがあるかもしれないと思うと、やっぱり経済学はよくわからない。
成功しやすい名前・失敗しやすい名前のリストは面白かった。

世紀の空売り―世界経済の破綻に賭けた男たち

サブプライム危機に賭けて大儲けした人の小説的な本。空売りするために保険を買い集めるみたいな手を駆使して利益を手にする過程は面白かった。

貨幣の「新」世界史――ハンムラビ法典からビットコインまで

貨幣の「新」世界史――ハンムラビ法典からビットコインまで

貨幣の「新」世界史――ハンムラビ法典からビットコインまで

貨幣の歴史を紐解く本なのだが、作者が勉強したことをまとめましたという感じであまり深い話がなくそこまで面白くなかった。

政治っぽい本

永続敗戦論――戦後日本の核心

近年の日本の政治的問題点が日本が敗戦を直視してこなかったことに起因すると論じた本。「鳩山首相が基地の県外移設に失敗して辞任したのは日本国民の意向よりもアメリカの意向が反映された結果で、日本の主権が日本にないことを示した事例」みたいな極端な物言いが多いのだが、ある程度の真実を捉えているように感じた。

自壊する帝国

自壊する帝国

自壊する帝国

ソ連崩壊時に外交官として情報収集にあたっていた人の自伝的な本。大きな流れはよく分からないが、当時の雰囲気を知るにはよい本。

たのしいプロパガンダ

たのしいプロパガンダ (イースト新書Q)

たのしいプロパガンダ (イースト新書Q)

プロパガンダはエンターテイメントの形を取って国民に浸透するという過去の事例を研究した本。ガルパンなどの軍事アニメについて作者が言及していたのを見て読んだ。

その他のまじめっぽい本

グッド・マス ギークのための数・論理・計算機科学

グッド・マス ギークのための数・論理・計算機科学

グッド・マス ギークのための数・論理・計算機科学

情報科学科でやる内容についてごく浅く触れた本。こういうトピックが存在するということを軽くあさるにはいいかも。

フォークの歯はなぜ四本になったか 実用品の進化論

フォークの歯はなぜ四本になったか 実用品の進化論 (平凡社ライブラリー)

フォークの歯はなぜ四本になったか 実用品の進化論 (平凡社ライブラリー)

身の回りのモノについてあまり考えたことのない歴史を見ていく本。まとまりがなくてそんなに面白くなかったが、どんなものにもつくった人の歴史があるのだなぁと感じさせられた。

今年勉強した本

ルベーグ積分入門―使うための理論と演習

ルベーグ積分入門―使うための理論と演習

ルベーグ積分入門―使うための理論と演習

一番時間をかけて勉強した。今までの数学の勉強の仕方を反省させられた。

確率論

確率論 (岩波基礎数学選書)

確率論 (岩波基礎数学選書)

ルベーグ積分を勉強したのはこの本を読むため。上の本で最後の章で出てくる内容をほとんど説明なくバンバン使っていくので本当にルベーグ積分を読んでおいてよかった。
いままで雑に扱っていた確率を数学的に扱うとこうなるのかという驚きが読むたびにあって面白い。まだ途中なので2017年も継続して読む。

Combinatorial Optimization

Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics)

Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics)

組み合わせ最適化の本。蟻本とかであまり真面目に証明しなかったアルゴリズムに厳密っぽい証明が与えられているのだが、分からせるように書いたとは思えないくらい行間が広くて読むたびにつらくなる。あまり人に薦めたくない。

数値計算の常識

数値計算の常識

数値計算の常識

今年一番印象に残った本。ただの計算だと思っていたことにもたくさん考えることがあるのだと気付かされてとても面白い。

量子論の基礎―その本質のやさしい理解のために

量子論の基礎―その本質のやさしい理解のために (新物理学ライブラリ)

量子論の基礎―その本質のやさしい理解のために (新物理学ライブラリ)

量子コンピュータを勉強するために量子論を勉強しようと思って読んだ。実験から構成していく一般的な教科書とは異なり、基本的ルールから量子論を構成していく立場をとっていて確かに分かりやすいのだが、具体的現象が全然出てこないので本当に分かったのか分かってないのかよく分からなくなる。

これなら分かる最適化数学―基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで

最適化の説明が分かりやすくていい。

深層学習 Deep Learning

深層学習 Deep Learning (監修:人工知能学会)

深層学習 Deep Learning (監修:人工知能学会)

深層学習の定番入門書。そんなに分かりやすくないしもっといい本が出てくれないかなと常々思っている。

データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズ

緑本として知られるベイズ解析の入門書。とても分かりやすいが使われているソフトが今では主流ではなくなっているのでStanの本とかも読んだほうがいいかもしれない?

劣モジュラ最適化と機械学習

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

最近はやりの劣モジュラ最適化についての本。劣モジュラとは何かという話は分かりやすいのだが、これだけ読んでも劣モジュラのことが分かった気にはなれないしもっとちゃんと勉強しないとダメそう

生命情報処理における機械学習 多重検定と推定量設計

生命情報処理における機械学習 多重検定と推定量設計 (機械学習プロフェッショナルシリーズ)

生命情報処理における機械学習 多重検定と推定量設計 (機械学習プロフェッショナルシリーズ)

配列情報から遺伝子領域を推測する話とかを期待して読んだのに多重検定でp値をどうするかやアラインメントなどを推定量設計の面から統一的に見る話など、それ機械学習か?というトピックが多くて面白くなかった。

機械学習プロフェッショナルシリーズは「帯に短し襷に長し」という感じの本ばかりという印象を持ったのでこの2冊以外買ってない。


来年もいろいろな本を読んで楽しみ、勉強もしていきたいと思います。

おまけ

2016年に見たアニメ

全話見たものだけ

夏アニメ

秋アニメ

アセンブリ言語 その2

この記事はkivantium Advent Calendarの19日目です。

前回は最初のCPUの設計に使う命令セットを紹介しました。
今回はこの命令を使っていろいろなプログラムを書いてみます。

SPIM

ここではMIPSのシミュレータとして有名なSPIM (MIPSを逆から読んだ名前) を使うことにします。
GUIがついたQtSPIMをダウンロード・インストールします。

QtSPIMはアセンブリで書いたテキストファイルを読み込んで実行します。
実行したいファイルを保存して、File > Reinitialize and Load Fileとすることでファイルが読み込まれます。
再生ボタンのようなRun/Continueを押すと実行されます。

最初のプログラム

まずはHello, World代わりに数字の1を表示することにします。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $a0, $zero, 1     # $a0 に $zero+1 (=1) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

syscall$v0に入っている値に応じて異なる処理を行います。
SPIMの場合は1$a0に入っている整数を表示するprint_int、10でプログラムを終了するexitになります。
実装するCPUにはsyscall命令はありませんが、SPIMで結果を表示するためにしばらく使うことにします。

これを実行すると

1

となって、意図通り1が表示されます。

演算命令を使う例

演算命令はレジスタに演算を行った結果をレジスタに格納します。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    addiu $s1, $s0, 2       # $s1 に $s0+2 (=3) を入れる
    addu  $s1, $s0, $s1     # $s1 に $s0+$s1 (=4) を入れる
    sll   $a0, $s1, 2       # $a0 に $s1 を2bit左にシフトした値 (=16) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

これを実行すると

16

となります。

ロード・ストア命令

ロード命令は指定したアドレスのメモリ値をレジスタに入れ、ストア命令はレジスタの値を指定したアドレスに入れます。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    sw    $s0, -4($sp)      # $s0 の値をメモリアドレスが $sp-4 の領域に入れる
    lw    $a0, -4($sp)      # $a0 にメモリアドレスが $sp-4 の領域の値を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

$spは後で説明するスタックポインタが入っているレジスタです。同じ場所にストアしてからロードしているので出力は

1

となります。

ジャンプ命令とラベル

ジャンプ命令は次の命令のアドレスを指定してプログラムカウンタを変更します。
命令のアドレスを数字で明示的に書くのは大変なので普通はラベルを使用します。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    j     jumpto            # jumpto というラベルまでジャンプ
    addiu $s0, $zero, 2     # $s0 に $zero+2 (=2) を入れる
jumpto:                     # ジャンプ先のラベル
    addiu $a0, $s0, 0       # $a0 に $s0+0 (=$s0) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

これを実行すると

1

が表示されます。jumpの次の行の$s0に2を入れる処理がジャンプで飛ばされていることが確認できます。

条件分岐命令

条件分岐命令は比較結果に応じて次のプログラムカウンタを変更する命令です。

    .text                    # アセンブリ命令がここから始まることを示す
main:                        # main関数を表すラベル
    addiu $s0, $zero, 1      # $s0 に $zero+1 (=1) を入れる
    addiu $s1, $zero, 2      # $s1 に $zero+2 (=2) を入れる
    beq   $s0, $s1, if_equal # $s0 と $s1 が等しければif_equalへ行く
    addiu $a0, $zero, 0      # $a0 に $zero+0 (=0) を入れる
    j     display            # display にジャンプ
if_equal:                    # ラベル
    addiu $a0, $zero, 1      # $a0 に $zero+1 (=1) を入れる
display:                     # ラベル
    addiu $v0, $zero, 1      # $v0 に $zero+1 (=1) を入れる
    syscall                  # システムコール (print_int)
    addiu $v0, $zero, 10     # $v0 に $zero+10 (=10) を入れる
    syscall                  # システムコール (exit)

これはC言語でいうと

s0 = 1; s1 = 2;
if(s0 == s1) a = 1;
else         a = 0:
printf("%d", a);

アセンブリで書いたイメージです。実行結果は

0

となります。

関数呼び出し

アセンブリでの関数は「特定のレジスタに引数を入れた状態で関数の動作が書かれた部分にジャンプした後、特定のレジスタに戻り値を入れた状態で元の場所に戻る処理」として表現されます。
MIPSの場合、引数は$a0$a3に、戻り値は$v0$v1に入れることになっています。

簡単な例を見てみます。

    .text                    # アセンブリ命令がここから始まることを示す
main:                        # main関数を表すラベル
    addiu $a0, $zero, 1      # $a0 に $zero+1 (=1) を入れる
    jal   func               # funcを呼び出す
    addu  $a0, $v0, $zero    # a0 に $v0 (戻り値) を入れる
    addiu $v0, $zero, 1      # $v0 に $zero+1 (=1) を入れる
    syscall                  # システムコール (print_int)
    addiu $v0, $zero, 10     # $v0 に $zero+10 (=10) を入れる
    syscall                  # システムコール (exit)
func:
    sll   $v0, $a0, 1        # $v0 に $a0 を左に1bitシフトした値を入れる
    jr    $ra                # $ra (関数を呼び出した次のアドレスが入る)にジャンプ

これはC言語でいうと

int func (int a) {
    return a << 1;
}
int main(void) {
    printf("%d", func(1));
}

に対応するコードのイメージです。結果は

2

となります。

関数を呼び出した後に元の位置に戻ることができるのはjal命令で$raに関数呼び出しの次のアドレスを格納しているため、関数が終わるときにjr命令で$raの値にジャンプできるからです。関数呼び出しが1回であればこの方法でいいのですが、呼び出した関数の中でもう一度関数を書くと$raが上書きされてしまいリターンアドレスが分からなくなってしまいます。これを回避するためにコールスタックと呼ばれるデータ構造を使います。

最後に格納した情報が最初に出てくるデータ構造をスタックといいます。スタックを用いると、関数を呼び出す際にリターンアドレスをスタックに入れて、関数を終了するときにスタックからリターンアドレスを取り出せばいくつ関数を呼び出しても正しい順番で戻ることができます。スタックをメモリ上に作るためにスタックポインタとフレームポインタという2つの値を使います。

スタックポインタはスタックの最下端のアドレスを表していて、スタックにデータを積むたびに値が減らされ、スタックからデータを取り出すと値が増やされます。
一つの関数を呼び出すたびにスタックに積まれるデータのひとかたまりをスタックフレームと呼び、フレームポインタからスタックポインタの間のアドレスがスタックフレームとなるようにフレームポインタの間の値がセットされます。

関数を呼び出すたびにリターンアドレス・フレームポインタ・スタックポインタをスタックに保管しておけば関数を呼び出しても復帰先が分からなくなることはありません。
スタックはリターンアドレスの他にもレジスタに入りきらない引数や退避したい変数を格納するのにも使います。
SPIMではmain関数が始まった時点で$sp$fpにその時のスタックポインタ・フレームポインタが入っています。

その他、ヒープ領域などのアドレス空間なども説明した方がいいかもしれませんが、今後の話に関係ないので省略します。

ではこれを使って再帰を使ったフィボナッチ数を計算する例を紹介します。
C言語のイメージコードは

int fib(int n) {
    if(n < 2) return 1;
    else return fin(n-1)+fib(n-2);
}
int main(void) {
    for(int i=0; i<15; i++) {
        printf("%d\n", fib(i));
    }
}

です。

アセンブリ

    .text
    .globl main
main:
    # スタックフレームの作成
    addiu   $sp, $sp, -32   # スタック領域を下に32 byte伸ばす
    sw      $ra, 20($sp)    # リターン・アドレスを退避
    sw      $fp, 16($sp)    # フレーム・ポインタを退避
    addiu   $fp, $sp, 28    # 新しいフレーム・ポインタを設定
    addiu   $s0, $zero, 0
    addiu   $s1, $zero, 10
    addiu   $s2, $zero, 2
loop:
    beq     $s0, $s1, end
    addu    $a0, $s0, $zero # fibの引数に$s0を設定
    jal     fib             # fibを呼び出す
    addu    $a0, $v0, $zero # fibの結果をa0に移動
    addiu   $v0, $zero, 1   # syscallでprint_intを呼び出す設定
    syscall                 # print_intでa0(fibの結果が入る)を出力
    addiu   $a0, $zero, 10 
    addiu   $v0, $zero, 11
    syscall
    addiu   $s0, $s0, 1
    j       loop
end:
    lw      $ra, 20($sp)    # 退避したリターン・アドレスを復元
    lw      $fp, 16($sp)    # 退避したフレーム・ポインタを復元
    addiu   $sp, $sp, 32    # スタック領域を32 byte短くする
    jr      $ra             # 呼び出し元に戻る
# fib関数
fib:
    addiu   $sp, $sp, -32   # スタック領域を下に32 byte伸ばす
    sw      $ra, 20($sp)    # リターン・アドレスを退避
    sw      $fp, 16($sp)    # フレーム・ポインタを退避
    addiu   $fp, $sp, 28    # 新しいフレームポインタを設定
    sw      $a0, 0($fp)     # a0 (引数)を退避
    slt     $t0, $a0, $s2   # (次の行と合わせて) a0<2ならば$L2にジャンプ
    beq     $t0, $zero, L2      
    addiu   $v0, $zero, 1   # (ここはa0==0のとき実行される) v0(戻り値)に0を入れる
    j       L1              # $L1にジャンプ
# fibの再帰部分
L2:
    lw      $a0, 0($fp)     # 退避しておいたnを$a0に入れる
    addiu   $a0, $a0, -1    # $a0 <- $a0 - 1
    jal     fib             # fib(n-1)の再帰呼出し
    sw      $v0, 4($fp)     # fib(n-1)の戻り値を退避
    lw      $a0, 0($fp)     # 退避しておいたnを$a0に入れる
    addiu   $a0, $a0, -2    # $a0-2を求める
    jal     fib             # fib(n-2)の再帰呼出し
    lw      $v1, 4($fp)     # v1に退避しておいたfib(n-1)の値を入れる
    addu    $v0, $v0, $v1   # v0(fib(n-2)の戻り値)にfib(n-1)の値を足す
# fib関数の終了処理
L1:
    lw      $ra, 20($sp)    # 退避したリターン・アドレスを復元
    lw      $fp, 16($sp)    # 退避したフレーム・ポインタを復元
    addiu   $sp, $sp, 32    # スタック領域を32 byte短くする
    jr      $ra             # 呼び出し元に戻る

結果は

1
1
2
3
5
8
13
21
34
55

となります。

以上の説明で前回の命令セットがある程度実用的なCPUとして十分な機能を持っていることが分かったと思います。
次回(いつになるかは分かりませんが)はこの再帰フィボナッチが動くCPUを実際にVerilogFPGA上に作成します。

参考

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 上

アセンブリ言語 その1

この記事はkivantium Advent Calendarの18日目です。

CPUを設計する際に重要な要素の一つが命令セットアーキテクチャ (ISA) です。 これから設計する簡単なCPUのISAとして、分かりやすく参考文献も多いMIPSを採用することにしました。 MIPS ISA の詳細は https://www.cs.cornell.edu/courses/cs3410/2008fa/mips_vol2.pdf が詳しいです。

CPUの構成

昨日の記事で見たように歴史上様々なCPUが存在しており、CPUはこういう形だと言い切るのは難しいのですが、現在生き残っている多くのCPUはレジスタマシンになっています。

レジスタマシンを構成する主な要素は

プログラムカウンタ (PC)
現在行っている命令の番号を保持します
命令メモリ
CPUが実行する命令を保持します
汎用レジスタ
計算する値や計算結果を格納します
ALU
汎用レジスタの値や命令で指定された値(即値)を入力として受け取り、命令によって指定された計算を行います
データメモリ
汎用レジスタに入りきらないデータの格納や外部との通信などを行います

となっています。

(注: 実際にはデータメモリと命令メモリは同じものであることが多かったりしますが、概念を理解するために詳細は省きます)

これらの要素に対する操作を直接記述していくのが機械語によるプログラムで、バイナリで記述されます。バイナリでプログラムを書くのは人間には厳しいので機械語に対応する命令列をアルファベットで記述できるようにしたのがアセンブリ言語です。

アセンブリ命令の種類

以後しばらくの実装に使う命令セットを種類ごとに紹介します。

演算命令

レジスタ同士の加算やANDなどのいわゆる演算っぽい命令です。

命令 記法 処理
addiu addiu rt, rs, immediate R[rt] ← R[rs] + SignExtImm
addu addu rd, rs, rt R[rd] ← R[rs] + R[rt]
and and rd, rs, rt R[rd] ← R[rs] & R[rt]
or or rd, rs, rt R[rd] ← R[rs] | R[rt]
sll sll rd, rt, shamt R[rd] ← R[rt] << shamt
srl srl rd, rt, shamt R[rd] ← R[rt] >> shamt
slt slt rd, rs, rt R[rd] ← (R[rs] < R[rt]) ? 1 : 0
subu subu rd, rs, rt R[rd] ← R[rs] - R[rt]
  • R[rt]は「rtで指定された番号の汎用レジスタ」を意味します。
  • SignExtImmは指定された即値の符号拡張(最上位bitを必要なだけコピーして付け加えたもの)を表します。

ロード・ストア命令

データメモリへの格納を行う命令です。

命令 記法 処理
lw lw immediate(rs) R[rt] ← Memory[R[rs] + SignExtImm]
sw sw immediate(rs) Memory[R[rs] + SignExtImm] ← R[rt]
  • Memory[R[rs] + SignExtImm]は「rsで指定された番号の汎用レジスタに入っている値に符号拡張した即値を足した値をアドレスに持つメモリ」を意味します。

ジャンプ命令

次の命令のアドレスを指定してプログラムカウンタを書き換える命令です。

命令 記法 処理
j j address PC ← {(PC+4)[31:28], address, 00}
jal jal address PC ← {(PC+4)[31:28], address, 00}; R[31] ← (PC+4)
jr jr rs PC ← R[rs]

条件分岐命令

条件が成立したかどうかに応じて次の命令が変わる命令です。if文やfor文の実装などに不可欠な命令です。

命令 記法 処理
beq beq rt, rs, immediate if(R[rt]==R[rs]) PC ← (PC+4) + (SignExtImm<<2)
bne bne rt, rs, immediate if(R[rt]!=R[rs]) PC ← (PC+4) + (SignExtImm<<2)

命令フォーマット

これらの命令はアセンブリ言語として書いた後、アセンブラというソフトでバイナリ列に変換する必要があります。ここで扱うMIPS 32の場合全ての命令は32bitの値として表されます。フォーマットにはR, I, Jの3種類あります。

R format

汎用レジスタ2つを演算して汎用レジスタに格納する命令はR formatになります。

命令 op rs rt rd shamt funct
addu 000000 XXXXX XXXXX XXXXX 00000 100001
and 000000 XXXXX XXXXX XXXXX 00000 100100
jr 000000 XXXXX 00000 00000 00000 001000
nor 000000 XXXXX XXXXX XXXXX 00000 100111
or 000000 XXXXX XXXXX XXXXX 00000 100101
sll 000000 00000 XXXXX XXXXX XXXXX 000000
srl 000000 00000 XXXXX XXXXX XXXXX 000010
slt 000000 XXXXX XXXXX XXXXX 00000 101010
subu 000000 XXXXX XXXXX XXXXX 00000 100011

I format

汎用レジスタ2つと即値に対する処理を行う命令はI formatになります。

命令 op rs rt immediate
addiu 001001 XXXXX XXXXX XXXXXXXXXXXXXXXX
beq 000100 XXXXX XXXXX XXXXXXXXXXXXXXXX
bne 000101 XXXXX XXXXX XXXXXXXXXXXXXXXX
lw 100011 XXXXX XXXXX XXXXXXXXXXXXXXXX
sw 101011 XXXXX XXXXX XXXXXXXXXXXXXXXX

J format

汎用レジスタを指定せずに長い即値を使う命令はJ formatになります。

命令 op address
j 000010 XXXXXXXXXXXXXXXXXXXXXXXXXXX
jal 000011 XXXXXXXXXXXXXXXXXXXXXXXXXXX

レジスタの使い方

MIPSには汎用レジスタが32個あり、以下のように使い分けることになっています。

名称 番号 用途 呼び出された側が内容を保存する必要があるか?
$zero $0 読み出すと常に0 N/A
$at $1 アセンブラが一時的に使用 No
$v0-$v1 $2-$3 関数の戻り値や式を評価した結果 No
$a0-$a3 $4-$7 関数の引数 No
$t0-$t7 $8-$15 一時変数 No
$s0-$s7 $16-$23 一時変数だがセーブされる Yes
$t8-$t9 $24-$25 一時変数 No
$k0-$k1 $26-$27 OSのカーネル用に予約 No
$gp $28 広域(グローバル)ポインタ Yes
$sp $29 スタックポインタ Yes
$fp $30 フレームポインタ Yes
$ra $31 リターンアドレス N/A

次回はこれらの命令をつかってアセンブリ言語でどのようにプログラムを書くのか見ていきます。

いろいろなCPU

この記事はkivantium Advent Calendarの17日目の記事です。

昨日まででCPUを作る部品の解説は一通り終わったのでついにCPUの作成に入る準備ができました。
実際に作成に入る前に過去の偉人に学ぶべく独断と偏見で選んだ歴史上のCPUたちを一言ずつ紹介していきます。
CPUという分類に入らないものもありますがまぁ適当に。

1944年 Harvard Mark I(IBM

ハーバード・アーキテクチャの由来。

1946年 ENIACペンシルベニア大学

アメリカ陸軍の弾道研究室での砲撃射表の計算用に設計された。十進法で10桁の数値を記憶していた。

1951年 EDVAC(ペンシルベニア大学

プログラム内蔵方式を採用していて、フォン・ノイマンがEDVACについての論文を発表したことから、ノイマンアーキテクチャと呼ばれるようになった。二進数が採用されている。

1964年 System/360 (IBM)

IBMによるメインフレーム コンピュータのシリーズ。このシリーズの成功により大型コンピュータにおける米国メーカーの出荷高の7割以上をIBMが占めることになった。Out-of-Order実行に用いられるTomasuloのアルゴリズムは1967年に考案され、IBM System/360 Model 91に実装された。

1964年 CDC6600

世界で初めて成功したスーパーコンピュータで、当時の最速のマシンの三倍程度の性能とされる。また、最初期のRISCとも言われている。

当時のIBMのCEOがCDC6600に負けたことに怒って書いた以下のメモは有名。


http://www.computerhistory.org/revolution/supercomputers/10/33/62

1970年 PDP-11 (DEC)

16ビットミニコンピュータシリーズで、後のプロセッサやOSに影響を及ぼし、C言語の仕様にも影響を与えたと言われている。Version 6 Unixが動くことでも有名。

1971年 4004 (Intel)

最初期の4ビットマイクロプロセッサ。Intelの最初のCPUというとこれが挙げられることが多い?

1976年 Cray-1 (クレイ・リサーチ)

当時世界最高速のベクトル型スーパーコンピュータ。

デザインが本当に好き。

かっこいい。

1976年〜 VAX (DEC)

PDP-11の拡張。典型的なCISC ISAと言われている。

1978年 8086 (Intel)

x86シリーズ最初となる16ビットプロセッサ。MS-DOSなどが動いた。

1980年 MC68000モトローラ

8086のライバルとしてよく取り上げられるが、全く知らないので言及は控える。

1982年 RISC-I (カリフォルニア大学バークレー校)

パターソン(RISCという単語を作った人)らのチームによって開発されたプロセッサ。SPARCなどに影響を与えた。レジスタ・ウィンドウを採用しているらしい。
写真は発見できなかった。

1983年 トランスピュータ (インモス)

並列コンピューティングに特化した初めての汎用マイクロプロセッサ

1983年 SX-2 (NEC)

世界で最初にGFLOPSを超えたスーパーコンピューター。
SXシリーズはベクトル型スーパーコンピュータ最後の生き残りとして頑張っている。当時世界最速ということで有名な地球シミュレータはSXシリーズがベース

http://museum.ipsj.or.jp/computer/super/0008.html より

1985年 MIPS R2000 (ミップス・コンピュータシステムズ)

ヘネシーらのチームによって開発されたRISCの代表的なプロセッサ。今後しばらくはMIPSベースのアーキテクチャで開発を進める。

1985年 SPARC

RISCの代表選手と言えるプロセッサ。SPARC64は京に採用されている。

1986年 ARM2

ARMシリーズの最初の製品となるARM2はこの頃に出荷された。

1989年 Intel i860 (Intel)

IntelによるRISCプロセッサ。VLIWアーキテクチャを採用していた。
商業的には全く成功しなかった。

1992年 DEC Alpha

VAXの後継として作られた。Windowsも動いていたがWindows 2000でサポートが打ち切られてしまった。

2001年 Itanium (Intel)

高性能サーバ向けの命令セットアーキテクチャであるIA-64を初めて採用したCPU。x86の置き換えを狙っていたという噂だが、バイナリ互換の壁には勝てず商業的にはあまりうまくいっていないらしい……

このようにコンピュータの歴史ではたくさんのCPUが生まれては死んでいったわけです。出典が特に無い画像はWikipediaへの直リンクです。