ぱたへね!

はてなダイアリーはrustの色分けができないのでこっちに来た

The RISC-V Reader: An Open Architecture Atlas

パターソン先生の動画を見て、これは読まねばならぬと思い読んでみました。

https://www.amazon.com/RISC-V-Reader-Open-Architecture-Atlas/dp/0999249118/

Amazon.co.jpでは取り扱ってないけど、.comでは普通に買えます。不当に高いのをつかまないように。

プロセッサ大反省会の乗りで楽しく読めました。命令セットの説明も結構取ってあります。読むところのボリュームはそれほど多くないです。RISC-Vプログラマでも無い限り、細かい命令セットを覚えてもしょうが無いので、面白いところだけ読めば良いかと。

面白いのは設計上の判断するにあたって、どういう観点で判断したのかが明確になっています。

  • cost
  • simplicity
  • performance
  • isolation of architecture from implrementation
  • room for growth
  • program size
  • case of programming / compiling / linking

こういう話は開発者の中で閉じていて、外部にストレートに出てくることは少ないので勉強になりました。

20年くらいたったら、貴重な資料になりそうです。全てのプロセッサ好きにお勧めです。

GCPでTPUを使えるようにする

GCPでTPUを使いたくて試行錯誤した途中経過です。

コンソールからの登録

GCPコンソールの左上からTPUを登録しようとしても、なかなか上手く行かず挫折。 結局 ip address rangeに何を入れて良いのか分かりませんでした。

ctpuコマンドを使う

ctpuコマンドをCloud shellから使う方法で上手く行きました。最初はctpuコマンドが使えなかったのですが、TPUのチュートリアルをこなしたところ、いつの間にか使えるようになってました。

gcloud config set compute/zone asia-east1-c
gcloud config set compute/region asia-east1

ctpu up -name emiru -preemptible true

ctpuコマンドが使えるようになれば、ゾーンとリージョンを指定してctpu upでTPUノードが登録されました。

京都Devかふぇ#4 〜レガシーシステム考古学〜

京都Devかふぇ#4 〜レガシーシステム考古学〜にLT参加してきました。

僕の発表資料です。

どの人の発表もすごく面白かったです。

レガシーコードとの戦いの軌跡

レガシーから脱出するために、レビューにきっちりと時間を取って、ちゃんと管理しているのがすごいと思いました。 リーダブルコードは良書なのでぜひみんなに読んでもらいたいです。

iPhone OSアプリ開発の昔話

「脱獄」って最近聞かなくなりましたね。って所だけ理解できました。 なんだかんだ言って、開発者とユーザーに必要な機能、環境が少しずつ整備されている感じかなと。

データセンターの話

IDEってFPGA直結できるから好きなI/Fなんですが、めちゃくちゃレガシー扱いされていて泣いた。 レガシーを包み込むための仮想化技術の使い道が面白かったです。

fmty さん

レガシーなコミュニケーションツールの話。 同じような悩みをかかえていて笑いました。 複数で編集できるようにGoogle spreadsheetを提案したけど、結局Excelに戻った悲しさを思い出しました。最近のサービスってIEが対象外だったりするので、MSさんには責任をもってIEを駆逐して欲しいです。

takey さん

VB6まだまだ現役。定年の引き上げの流れの中、VB6もまだまだ生き残ると思います。 昔のVB6アプリケーションがそのまま動く、マイクロソフトとインテルの頑張りはもっと評価されて良いと思います。

mkashima さん

Windows95の愛されっぷりが良く分かるLTでした。 プレゼン資料の作り込みがすごかった。 brew cask でwindowsがインストールできるぞ!twitter.exeもあるぞ!

最後に

フリューさんってどこかで聞いた会社だと思ったら、アンチェインブレイズの会社じゃないですか。 まさかのアンチェインブレイズ遊んだ人とリアルで話す事ができました。次は開発した人に会いたいですね。 続編期待しています!

Rustの配列操作メモ

Rust Standard Library Cookbook から、気になった配列の操作をメモしました。

要素の取りだし

配列の要素を取り出すにはgetを使います。Option型で返ってくるので、Someかunwrapでその値を取り出せます。[ ]でも同じ動きです。

[ ]を使って配列の領域外にアクセスした場合は、回復できないので実行時エラーとなります。

    //配列要素の取り出し
    let cpus = vec!["sh", "x86", "arm", "mips"];

    //getで取り出す。
    let second_cpu = cpus.get(1);
    if let Some(second_cpu) = second_cpu {
        println!("second spu = {}", second_cpu);
    }

    //unwrap
    let last_cpu = cpus.last().unwrap();
    println!("last_cpu = {}", last_cpu);

    //no check
    let first_cpu = cpus[0];
    println!("first cpu = {}", first_cpu);

    //error
    //let cpu = cpus[10];
    //println!("cpu = {}", cpu);

重複の削除

dedup()を使うと、連続する重複する要素が1つにまとめられます。完全に重複を無くしたい場合は、sort()してから、dedup()を使います。

    //重複の削除
    let mut nums = vec![1, 2, 2, 2, 3, 3, 4, 5, 1, 5];
    nums.dedup();
    println!("deduped {:?}", nums);
    // deduped [1, 2, 3, 4, 5, 1, 5]

    let mut nums = vec![1, 2, 2, 2, 3, 3, 4, 5, 1, 5];
    nums.sort();
    nums.dedup();
    println!("deduped {:?}", nums);
    //deduped [1, 2, 3, 4, 5]

分割と結合

split_off()で分割して、append()で結合します。所有権も上手くやってくれます。

    let mut cpus = vec!["sh", "x86", "arm", "mips"];
    let mut later = cpus.split_off(2);
    println!("cpus = {:?}, later = {:?}", cpus, later);
    //cpus = ["sh", "x86"], later = ["arm", "mips"]

    cpus.append(&mut later);
    println!("cpus = {:?}, later = {:?}", cpus, later);
    //cpus = ["sh", "x86", "arm", "mips"], later = []

retain

配列から特定の要素だけを取り出します。何気に破壊的操作です。

    //retain
    let mut cpus = vec!["sh", "x86", "sh2", "sh4", "arm", "mips"];
    cpus.retain(|name| name.starts_with("sh"));
    println!("cpus = {:?}", cpus);
    //cpus = ["sh", "sh2", "sh4"]

drain

配列から要素を取り出したら、そのまま削除して欲しいときに使います。キュー的なアルゴリズムで活躍しそうです。

下の例は、配列cpusから先頭から二つを取り出して何かに使った後、取り出した分だけが配列から削除されます。

    //drain
    let mut cpus = vec!["sh", "x86", "sh2", "sh4", "arm", "mips"];
    for cpu in cpus.drain(..2) {
        println!("use {}", cpu);
    }
    println!("cpus {:?}", cpus);
    //cpus ["sh2", "sh4", "arm", "mips"]

swap_remove

Rustっぽい面白い操作です。通常、配列から要素を一つ削除すると、削除した後の要素をコピーして空白を埋める必要があります。swap_removeを使うと、削除した場所に最後の要素を入れて配列の大きさを一つ小さくすることで、要素のコピーを防ぎます。

下の例では、2を取り出して削除した後、空いた場所に配列の最後の要素6を入れることで、配列のコピーを防いでいます。

    let mut nums = vec![1, 2, 3, 4, 5, 6];
    let second_num = nums.swap_remove(1);
    println!("nums = {:?}, second_num = {}", nums, second_num);
    //nums = [1, 6, 3, 4, 5], second_num = 2

組合せ最適化アルゴリズムの最新手法―基礎から工学応用まで

組合せ最適化アルゴリズムの最新手法―基礎から工学応用までを読みました。

80年代後半、90年代の論文がよく出てきており、20年前の最先端をまとめた本です。題材に半導体関連のネタが多く、興味を持って最後まで読めました。シミュレーティド・アニーリング手法(SA)、遺伝的アルゴリズム(GAs)、タブー・サーチ手法(TS)、シミュレーティド・エボリューション手法(SimE)、確率的進化手法(StocE)について分かりやすく書いてありました。 ただ、この本を読んで実際の問題を解けるかどうかといわれると難しい気がします。

組み合わせ最適化について

この本にのっているアルゴリズムは、基本的にはすべてこのような手順になっています。

  • 上手い初期値を設定する
  • 上手く少しだけ良い方向へ変化する
  • 上手く局所解を抜けて、大域解へ向かう。

局所解を抜けるために、どこかで乱数を使います。各アルゴリズムの違いはどこを重視するかです。 遺伝的アルゴリズムであれば、初期値を大量に作り生き残りを作っていくことで、上手い初期値としています。 タブーサーチ方では上手く良い方向へへの変化を求めるときに、過去の失敗をタブーとして参考にします。

直行している概念も多く、最後の章ではそれぞれの組み合わせの考察もありました。

実際はこのアルゴリズムにかける前に、上手いモデルの定義があって、それはそれで見るからに面倒でした。上手く行った事例が結構載っているのですが、それ以外は上手く行かなかったんだろうなという感じです。

並列コンピューティングやSIMDへの期待が高いのも興味深く読めました。

当時のニューラルネットワークの評価

面白いことに半導体の配置問題をニューラルネットワークを使って解くという89年の取り組みが紹介されています。30年前のニューラルネットワークの評価として貴重な資料です。

本の中では、このようにまとめられています。

ホップフィールド型ネットワークを配置問題に適用したユーの結果は、有望なものではなかった。いくつかの問題点は、シミュレーション時間が長いこと、解の質が低いこと、および、ネットワークのパラメータに対して、解の感度が高いことである。現段階では結論として、ニューラルネットワークを困難な最適化問題にてきようできるかどうかについては、さらに多くの研究が必要であると、述べるにとどめる。

RustでSimulated Annealing

本棚を見たら組合せ最適化アルゴリズムの最新手法―基礎から工学応用までという本を見つけました。Simulated Annealingのアルゴリズムが載っていたので、せっかくだからRustで実装してみました。

問題

f:id:natsutan:20181117082906p:plain

この図の回路を2つのエリアにわける方法を考えます。簡単のために、10個あるノード(ゲート)を5個、5個に分けることにします。ノードには1~10の通し番号が入っていて、それぞれのネットには分割時のコストが設定されています。

分ける時のコストがこのように定義されています。

net node cost
N1 {1, 2, 4, 5} 1
N2 {2, 3, 5} 1
N3 {3, 6, 10, 4} 2
N4 {4, 8, 3, 7} 1
N5 {5, 7, 1, 6} 3
N6 {6, 4, 7, 2} 3
N7 {7, 9, 5} 2
N8 {8, 2} 3
N9 {9, 10, 5} 2
N10 {10, 5} 4

ノードを接続しているネットにもN1~N10の通し番号が打ってあります。例えばn1は、1, 2, 4, 5のノードが接続されています。 ノードを2つに分割した結果、1, 2, 4, 5が同じエリアに存在する場合はコストは0、2つのエリアに分割された場合は1のコストが発生します。分割した結果のコストの和を最小化することが目的です。

このようにオレンジと緑に分割したとします。

f:id:natsutan:20181117082937p:plain

2つのエリアをまたぐネットは赤線にしています。赤線のネットに設定されているコストを全て足すと10になり、この分割をしたときのコストになります。

こういう問題を「最小集合2分割問題」と呼び、意外にもNP困難です。そこで、Simulated Annealingの出番です。

Simulated Annealingアルゴリズム

そんなに難しくない。初期値はランダムに2つに分割します。

  • 現在のコストを計算する。
  • ランダムに1つノードを入れ替える。
  • コストが下がった場合は、一つ上に戻りノードを入れ替える。
  • コストが上がる場合は、以下の確率でその分割を採用する。二つ上に戻り、ノードを入れ替える。

コストが悪くなってもその分割を採用する確率はこのように決められています。

P = e^{-\Delta C /T}

ΔCが新しいコストと現在のコストの差、Tは現在の温度です。時間と共に温度が下がっていきます。温度という概念がでてきましたが、基本的にはループの回数です。

やってみた結果

本に載っているとおりにやってみました。

f:id:natsutan:20181117090309p:plain

この回路の場合分割後のコストが10が最小のようなのですが、何回かやると10になっていることが分かります。ちなみにここで求めた10が最小かどうかはSimulated Annealingでは分かりません。

ソースコード

extern crate rand;

use rand::thread_rng;
use rand::Rng;
use rand::seq::SliceRandom;


struct Net {
    nodes:Vec<u32>,
    weight:u32,
}

type Block =  [u32; 10];

//ネットリストの定義
fn make_netlist() -> Vec<Net> {
    let mut netlist :Vec<Net> = Vec::new();

    let n1 = Net{nodes:vec![1, 2, 4, 5], weight: 1};
    let n2 = Net{nodes:vec![2, 3, 5], weight: 1};
    let n3 = Net{nodes:vec![3, 6, 10, 4], weight: 2};
    let n4 = Net{nodes:vec![4, 8, 3, 7], weight: 1};
    let n5 = Net{nodes:vec![5, 7, 1, 6], weight: 3};
    let n6 = Net{nodes:vec![6, 4, 7, 2], weight: 3};
    let n7 = Net{nodes:vec![7, 9, 5], weight: 2};
    let n8 = Net{nodes:vec![8, 2], weight: 3};
    let n9 = Net{nodes:vec![9, 10,  5], weight: 2};
    let n10 = Net{nodes:vec![10, 5], weight: 4};

    netlist.push(n1);
    netlist.push(n2);
    netlist.push(n3);
    netlist.push(n4);
    netlist.push(n5);
    netlist.push(n6);
    netlist.push(n7);
    netlist.push(n8);
    netlist.push(n9);
    netlist.push(n10);

    netlist
}

//ランダムにブロックを振り分ける
fn initial_block() -> Block {
    let mut rng = thread_rng();
    let mut new_block: Block = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    new_block.shuffle(&mut rng);
    new_block
}

//引数のnetが、ABどちらかのブロックに入っていればtrue
//AB両方のブロックにまたがっていればfalse
fn same_area(block:&Block, net:&Net) -> bool {
    let block_a = &block[0..5];
    let block_b = &block[5..10];
    //全てtrue、もしくは全てfalseの時trueを返す
    let contain_as: Vec<bool> = block_a.into_iter().map(|x| net.nodes.contains(x)).collect();
    let contain_bs: Vec<bool> = block_b.into_iter().map(|x| net.nodes.contains(x)).collect();

    let all_b = !contain_as.into_iter().fold(false, |all_a, x| all_a | x);
    let all_a = !contain_bs.into_iter().fold(false, |all_b, x| all_b | x);

    all_a || all_b
}

//分割後のcost計算
fn cost(block:&Block, netlist:&Vec<Net>) -> u32 {
    // blockの前半が、分割したエリアに全て入ればそのまま、そうで無ければそのネットに対応したweightを加算する。
    netlist.into_iter().fold(0,|cost, net| if same_area(&block, net) {cost} else {cost + net.weight} )
}

//ランダムに2つのノードを入れ替える
fn swap_node(block:&Block) -> Block {
    let mut new_block = block.clone();
    let mut rng = thread_rng();

    let choice_a = rng.gen_range(0, 6);
    let choice_b = rng.gen_range(6, 10);

    new_block.swap(choice_a, choice_b);
    new_block
}

#[test]
fn cost_test(){
    let netlist = make_netlist();
    let mut block:[u32; 10] = [2, 4, 6, 7, 8, 1, 3, 5, 9, 10];
    let cur_cost = cost(&block, &netlist);
    assert_eq!(cur_cost, 10)
}

//メトロポリス基準
// random < exp(- d_cost / t)
fn random(delta_cost:i32, t:f32) -> bool {
    let mut rng = thread_rng();
    let rand_value = rng.gen_range(0.0, 1.0);
    let d_cost:f64 = delta_cost as f64;

    rand_value < std::f64::consts::E.powf(- d_cost / t as f64)
}

//シミュレーテッドアニーリングの実行
fn simulated_annealing(mut t:f32, alpha:f32, beta:f32, max_time:f32, mut m:f32 , netlist:&Vec<Net> ) -> Block
{
    let mut cur_s :Block = initial_block();
    let mut time:f32 = 0.0;
    let mut best_s: Block = cur_s.clone();

    while {
        let result = metropolis(cur_s, best_s, t, m, netlist);
        cur_s = result[0];
        best_s = result[1];

        time = time + m * beta;
        t = alpha * t;
        m = m * beta;
        time < max_time
    } {}
    best_s
}

fn metropolis(mut cur_s: Block, mut best_s: Block, t:f32, m:f32, netlist:&Vec<Net>) ->[Block;2]
{
    let cur_cost = cost(&cur_s, netlist);
    let mut best_cost = cost(&best_s, netlist);


    for _x in 0 .. m as u32 {
        //ノードを一つランダムに交換
        let new_s = swap_node(&cur_s);
        let new_cost = cost(&new_s, netlist);
        let delta_cost = new_cost as i32 - cur_cost as i32;

        println!("new_cost = {} best_cost = {} block_a = {:?} block_b = {:?}", new_cost, best_cost,  &new_s[0..5], &new_s[5..10]);

        if delta_cost < 0 {
            cur_s = new_s;
            if new_cost < best_cost {
                best_s = new_s;
                best_cost = cost(&best_s, netlist);
            }
        } else {
            if random(delta_cost, t) {
                cur_s = new_s;
            }
        }
    }
    [cur_s, best_s]
}


fn main() {
    let netlist = make_netlist();

    let t0 = 10.0;
    let alpha = 0.9;
    let beta = 1.0;
    let m = 10.0;

    let best_block = simulated_annealing(t0, alpha, beta, 100.0, m, &netlist);
    let best_cost = cost(&best_block, &netlist);

    //最終結果
    println!("cost = {} block_a = {:?} block_b = {:?} ", best_cost,  &best_block[0..5], &best_block[5..10]);[f:id:natsutan:20181117082906p:plain]

}

まとめ

Vivadoの量子コンピュータ対応に期待したい。

rustでマクロ

rust standard library cookbookから。

マクロを使って、簡単な可変長引数を実現する例。

macro_rules! multiply {
    ( $last:expr ) => { $last };

    ( $head:expr, $($tail:expr), + ) => {
        $head * multiply!($($tail), +)
    };

}

fn main()
{
    let val1 = multiply!(2, 4, 8);
    println!("2 * 4 * 8 = {}", val1);

    let val2 = multiply!(2, 4, 8, 16);
    println!("2 * 4 * 8 * 16 = {}", val2);
}

マクロの中で再帰するのか。すごいな。