スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

計算機の基本原理を味わおう19 - 計算機と計算論

 この記事は、計算機の基本原理を味わおう18 - 計算機の原理とコンパイラの原理の続きです。前回は、計算機の原理からわかる、コンパイラの原理について解説しました。今回は、計算論について解説します。
 最小計算機も結構機能が整ってきましたので、今回は理論を解説します。今まで解説してきた計算機の基本原理は、チューリングマシンの概念を応用したものです。チューリングマシンは、計算というのものを抽象化したもので、計算論に含まれる概念です。具象的な事ばかりしていると理論がおろそかになるので、計算論もきっちりとやりましょう。プログラミング力は、実践と理論から生じます。両方向から実力を養いましょう。
 計算論と言っても身構える必要はありません。ばりばりプログラミングしている皆様にとって、ごく簡単なものしかありません。今回紹介する計算論の基礎知識もごくごく簡単なものです。しかし、簡単だといっても、とても役に立ちます。張り切って学びましょう♪
 ここで、改めてプログラムの実行を抽象化して考えてみましょう。抽象的に考えると、任意の入力値に対応して、1ステップ毎に計算機の状態を変えつつ進行しています。not命令を一例に挙げ、具体的に書くと・・・

cmov 2, 3 //手順0:実行フラグの場所に対象データを移動
cmov 0, 80 //手順1:手順5へジャンプ
cmov 2, 1 //手順2:比較フラグを真に設定
cmov 3, 1 //手順3:対象を1に設定
cmov 0, 96 //手順4:手順6へジャンプ
cmov 3, 0 //手順5:対象を0に設定
cmov 1, 0 //手順6:プログラムの終了。


対象となる値である入力値がtrue( 1 )のときは・・・
手順0 → 手順1 → 手順5 → 手順6

入力値がfalse( 0 )のときは・・・
手順0 → 手順1 → 手順2 → 手順3 → 手順4 → 手順6

という具合に1つずつ順番に実行していきます。計算論ではこの事を、手順を「状態」というと、入力値に応じて状態が遷移すると表現できます。細かい事を言うと、手順そのものではなく、その時の最小計算機の状態が問題なのですが、分かり難いので個々のプログラムを追っていきましょう。
 ここまでの説明で、「出力値は?」と思った人はセンスがいいです。最小計算機にも出力値が必要です。出力値を付け加えましょう。

using System;

namespace MiniBitMachine.V3
{
    //機械語命令を実行するオブジェクト。
    internal class Executer
    {
        //関係のないメンバーは省略
        
        //命令を実行する。
        public bool? Execute( CompareMove command )
        {
            bool? result = null;
            ExecuteType type = this.GetExecuteType( command );
            switch ( type ) {
                case ExecuteType.Normal:
                    command.Destination = 
                        this._addresser.GetDataAddress( command.Destination );
                    command.Source = 
                        this._addresser.GetDataAddress( command.Source );
                    command.Execute( this._referenceMemory );
                    break;
                case ExecuteType.UpdateCompareFlag:
                    command.Source = 
                        this._addresser.GetDataAddress( command.Source );
                    this._compareFlag =
                    this.ReferenceMemory.Read( command.Source );
                    break;
                case ExecuteType.UpdatePc:
                    this._addresser.ProgramCounter = 
                        ( byte ) command.Source;
                    break;
                //----- ここに注目! -----
                case ExecuteType.StopCpu:
                    this._isStop = true;
                    ushort address = this._addresser.GetDataAddress( 
                        command.Source);
                    result = this.ReferenceMemory.Read( address );
                    break;
                //-------------------------
                case ExecuteType.Nothing:
                    break;
                default:
                    throw new ArgumentException(
                        type + "には対応していません。" );
            }
            return result;
        }
    }
}

 これで、せっかく出力値が得られるようになったので、状態遷移を詳しく見てみましょう。

using System;

namespace MiniBitMachine.V3
{
    //実行結果
    public class ExecutionResult
    {
        //フェッチ時のメモリアクセス回数。
        public int FetchMemoryCount { get; set; }

        //デコード時のメモリアクセス回数。
        public int DecodeMemoryCount { get; set; }

        //実効時のメモリアクセス回数。
        public int ExecuteMemoryCount { get; set; }

        //計算機の出力。
        public bool? OutputValue { get; set; }

        //インスタンスの文字列表現を取得。
        public override string ToString()
        {
            var result = new System.Text.StringBuilder( );
            result.Append( "命令取得時のメモリアクセス回数:" );
            result.Append( this.FetchMemoryCount.ToString( ) );
            result.Append( Environment.NewLine );
            result.Append( "命令解析時のメモリアクセス回数:" );
            result.Append( this.DecodeMemoryCount.ToString( ) );
            result.Append( Environment.NewLine );
            result.Append( "命令実行時のメモリアクセス回数:" );
            result.Append( this.ExecuteMemoryCount.ToString( ) );
            result.Append( Environment.NewLine );
            result.Append( "計算機の出力値:" );
            result.Append( this.OutputValue.ToString( ) );
            result.Append( Environment.NewLine );
            return result.ToString( );
        }

        //加算
        public static ExecutionResult operator +( 
            ExecutionResult left, 
            ExecutionResult right )
        {
            var result = new ExecutionResult( );
            result.FetchMemoryCount =
                left.FetchMemoryCount + right.FetchMemoryCount;
            result.DecodeMemoryCount =
                left.DecodeMemoryCount + right.DecodeMemoryCount;
            result.ExecuteMemoryCount =
                left.ExecuteMemoryCount + right.ExecuteMemoryCount;
            return result;
        }
    }
}

using System;

namespace MiniBitMachine.V3.Utility
{
    //CPUオブジェクトに関する便利なメソッドを用意する。
    public static class CpuUtility
    {
        //3つの基本動作を連続して行う。
        public static ExecutionResult Run( this Cpu obj )
        {
            var result = new ExecutionResult( );
            obj.ReferenceMemory.Reset( );
            obj.Fetch( );
            result.FetchMemoryCount = obj.ReferenceMemory.AccessCount;
            obj.ReferenceMemory.Reset( );
            obj.Decode( );
            result.DecodeMemoryCount = obj.ReferenceMemory.AccessCount;
            obj.ReferenceMemory.Reset( );
            obj.Execute( );
            result.ExecuteMemoryCount = obj.ReferenceMemory.AccessCount;
            result.OutputValue = obj.Execute( );
            return result;
        }

        //CPUが停止するまで、
        //出力結果を表示しながら、
        //3つの基本動作を連続して行う。
        public static ExecutionResult AllRunAndShow( this Cpu obj )
        {
            Console.WriteLine( "状態遷移を表示" );
            var result = new ExecutionResult( );
            while ( !obj.IsStop ) {
                var temp = obj.Run( );
                result += temp;
                result.OutputValue = temp.OutputValue;
                string outStr = result.OutputValue == null ?
                    "なし" : result.OutputValue.ToString();
                Console.WriteLine( "実行命令[ {0} ] : 結果 {1}",
                    obj.Current,
                    outStr );
            }
            Console.WriteLine( );
            return result;
        }
    }
}

using System;
using System.Collections.Generic;
using MiniBitMachine;
using MiniBitMachine.V3;
using MiniBitMachine.V3.Utility;

class Sample
{
    //not命令を実行する。
    private static ExecutionResult NotExecute(
        byte ds,
        byte cs,
        Memory m,
        byte targetAddress,
        bool value )
    {
        Cpu cpu = new Cpu( ds, cs, m );
        ushort target =
            cpu.Addresser.GetDataAddress( targetAddress );
        m.Write( target, value );
        Console.WriteLine(
            "{0}の値が{1}の場合に、not命令を実行すると・・・",
            targetAddress,
            m.Read( target ) );
        var result = cpu.AllRunAndShow( );
        Console.WriteLine( "対象値:{0}",
            m.Read( target ) );
        Console.WriteLine( "状態" );
        Console.WriteLine( result );
        Console.WriteLine( );
        return result;
    }

    //not命令を試す
    private static ExecutionResult NotTest(
        byte ds,
        byte cs,
        byte targetAddress,
        Memory m,
        Not inc )
    {
        var result = NotExecute(
            ds, cs, m, targetAddress, true );
        var temp = NotExecute(
            ds, cs, m, targetAddress, false );
        result += temp;
        result.OutputValue = temp.OutputValue;
        return result;
    }

    //not命令を試すプログラムの開始部分
    private static void NotTestMain(
        Memory m,
        ExecuteEnvironment info,
        byte targetAddress,
        byte ds,
        byte cs )
    {
        Cpu cpu = new Cpu( ds, cs, m );
        Not not = new Not(
            targetAddress,
            cpu );
        not.SetBinary( );
        Console.WriteLine(
            "********** not命令の内容 **********" );
        Console.WriteLine( info );
        Console.WriteLine(
            "データセグメント:{0}",
            cpu.Addresser.GetDataAddress( 0 ) );
        Console.WriteLine(
            "コードセグメント:{0}",
            cpu.Addresser.GetCodeAddress( 0 ) );
        Console.WriteLine(
            "対象アドレス:{0}", 
            cpu.Addresser.GetDataAddress( targetAddress ) );
        Console.WriteLine( );
        Console.WriteLine( not );
        Console.WriteLine( );
        var result = NotTest(
            ds, cs, targetAddress, m, not );
        Console.WriteLine( );
        Console.WriteLine( "最終結果");
        Console.WriteLine( result );
    }

    static void Main()
    {
        Memory m = new Memory( );
        ExecuteEnvironment info = Cpu.GetEnvironment( );
        byte targetAddress = 3;
        byte ds = 0;
        byte cs = 1;
        NotTestMain( m, info, targetAddress, ds, cs );
        Console.ReadLine( );
    }
}

セグメントの関係上、アドレス部分がちょっと読みにくいと思いますが、これで状態ごとに出力値が変化する様子が見れるようになりました。なお、出力値はエラーの有無としており、true, false, nullの3値方式です。何故ならば、not命令は最終状態になるまで、エラーがないと断定できないからです。
 このように、入力値と出力値を有限の状態で扱うものを有限オートマトンといいます。ちなみに、より詳しく言うと、今回のサンプルプログラムは、途中で出力値が決定されず、最終的な状態のみで出力値が決まるのでムーア型順序機械と言います。
 not命令にはエラー状態がありませんが、普通のプログラムにはエラーがあります。エラー状態のときは、出力値が1になると考えてください。もちろん、出力値に何を定義するのかは様々ですが、始はエラーの有無で考えると理解しやすいです。
 今回はこれでお終いです。ただ漫然とプログラミングをするのではなく、計算論で抽象的に考えられるようになると、よりレベルアップできます。今回紹介した、初歩の初歩でも考え方を習得しておくと思考能力がアップします。これを機会に、ぜひ計算論を学習してください。続く・・・
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。