プログラミング・演習II

プログラミング・演習II
第１２回
簡易版
論理シミュレータの作成
田向
まとめとしてのの応用課題
簡単なコードを読んで慣れ，理解を深める。
計算機の中に物を作り、動かす体験をする。
コードの追い方、考え方を練習する。
デバッグの仕方も習得する。
０からは難しいので、既に出来ているものを
修正していく。
自由に考えられるようになるには、時間が掛
かるので、少しずつ練習する。
簡易論理シミュレータの作成
－要求仕様－
論理ゲート：
２入力AND： and(出力、入力１、入力２，遅延）;
２入力OR： or(出力、入力１、入力２，遅延）;
NOT：
not(出力、入力１，遅延）;
NullNode: 回路への入力( 1/0，遅延);
配線：
wire(出力、入力)；
時間：整数時間
論理回路：論理ゲートをつないだもの
verilogHDL をまねて module 回路名；
イベント・シミュレータ：
離散的に、ある時間ｔで論理値が
1→0、0→1へと変化する。
値の変化は内部遅延で入力端子から出力端子へ
“遅延”で伝わる。指定がない場合には遅延“０”
simulator
シミュレータ名
回路への入力は入力ポートに設定される。
Simulator の組み込み関数で実現
set（時間，値，入力ポート）
動作手順
1. シミュレーション対象を宣言する。
simulation sim;
Node::SimObj = &sim;
2. 回路を宣言する。
module test1;
3. 回路使用する配線の宣言を行う。
wire i1, i2, i3;
wire o1, o2, o3;
wire o4, o5, o6;
4. 使用する素子を宣言する。
nullNode in1(o1, i1)，in2(o2, i2)，
in3(o3, i3);
and and1( o4, o1, o2 ，２);
or or1 ( o5, o3, o4 ，１);
not not1( o6, o5 );
記述例
5．入力信号を設定する。
sim.set(0, 0, i1);
sim.set(0, 0, i2);
sim.set(0, 0, i3);
sim.set(10, 1, i3);
sim.set(25, 0, i3);
sim.set(30, 1, i1);
sim.set(35, 1, i2);
６．シミュレーションを行う。
for(int time=0; time< 100; time++)
{
sim.run(time);
cout<< time <<" : "<< and1.out <<" ,
"<< or1.out<<" , " << not1.out<<"\n";
}
タイムホイールとイベント
イベント・キュー
タイムホイール
イベント登録
タイムスロット
イベント実行
タイムホイール
時刻
時刻
素子
素子
値
値
時刻
時刻
素子
素子
値
値
時刻
時刻
時刻
素子
素子
素子
値
値
値
時刻
時刻
時刻
素子
素子
素子
値
値
値
プログラム
時刻
時刻
素子
素子
値
値
時刻
時刻
素子
素子
値
値
論理シミュレータの作成
論理素子： nodeから派生させる。
and → class and ： public node {…}
回路：リスト、または，双方向リストで作る。
信号変化：イベントevent クラス
処理手順；
1. イベント・キューから値を取り出す。
2. 素子で入力値を論理演算する。
3. 演算結果が前の値と違った時にはイベント発生
4. イベント・キューにイベントを積む
5. イベント・キューが空ならば終了。空でなければ、
１へ戻る
イベント・キュー：priority_queue で作る。
どうやって作る？既存の記述を利用する。
標準テンプレートライブラリmapを使用している。
既存のシミュレータ記述を利用して改変
Template（おさらい）
配列，stack，list：積む物が違うだけで
構造は同じ
特殊なテンプレート用の変数 T ：不特定
旧版 <class T> , 新版 <typename T>
Template<class T>
class Array { T* a; int size;
public: Array(int);
T& operator [ ](int index) };
Template<class T> //コンストラクタArray<T>::Array(int s):a(new T[size=s]) {
For( int I=0; I<size; I++) a[I]=0; }
Template<T>
T& Array<T>::operator[ ](int idx){
if(idx >=0 && idx <size) return a[idx];
return *new T;
キューのテンプレートによる構成例
Template<class T> class queue{
enum {size = 10};
T *q[size]; int in, out;
Public:
queue():in(0),out(0){ }
void add(T *I){ q[in++]=I; if(in>=size) in=0;}
T*get(){if(out==in) return 0;
T *result = q[out++];
if(out >=size) out=0;
return result;
}
使い方: クラス名 <パラメータ値> インスタンス名
queue <int> iq;
queue <String> sq;
テンプレートは複数の引数をもてる。
Template<class T, int sz> class buffer{
T v[sz];
.......…
}
関数テンプレート例
#include <iostream>
using namespace std;
template <class X> void swapargs(X &a, X &b)
{ X temp;
temp = a; a = b; b = temp;
}
int main( ){
int i=10, j=20;
float x=10.1, y=23.3;
cout << "オリジナル i, j: " << i << ' ' << j << endl;
cout << "オリジナル x, y: " << x << ' ' << y <<
endl;
swapargs(i, j); // 整数を入れ替える
swapargs(x, y); // floatを入れ替える
cout << "入れ替え後 i, j: " << i << ' ' << j << endl;
cout << "入れ替え後 x, y: " << x << ' ' << y <<
endl;
return 0;
}
単純な汎用リンクリスト
template <class data_t> class list {
data_t data;
list *next;
public:
list(data_t d);
void add(list *node) {node->next = this;
next = 0;
}
list *getnext() { return next; }
data_t getdata() { return data; }
};
template <class data_t> list<data_t>::list(data_t d)
{ data = d; next = 0; }
int main(){
list<char> start('a');
list<char> *p, *last;
・・・・・・・・・・
｝
汎用stackクラスの記述例
template <class StackT> class stack {
StackT stck[SIZE];
int tos;
// スタックの先頭の索引
public:
void init() { tos = 0; }
void push(StackT ch);
StackT pop();
};
template <class StackT>
void stack<StackT>:: push(StackT ob){
if(tos==SIZE) {
cout << "スタックは一杯です\n";
return;
}
stck[tos] = ob;
tos++;
}
Standard Template Library
Standard Template Library： STL
標準テンプレート・ライブラリ
再利用可能なライブラリ
を作る事がC++の主目標
STL例：map
priorityQueueやBinaryTreeは同じKey（Index)
を持つノードは一つだけ．
mapは同じKeyを持つノードを
いくつも持つことが出来る．
同時刻に動作するイベントは複数あるので
このmapが必要！
STL： map
map <key, T, Compare, Allocator>
型 key のユニークなキーでインデックス付け、
型Tの格納されている値へ高速にアクセス。
Compare： keyによる比較のための関数
Allocator：値を置くノードの構造．
map クラスのテンプレート
template
<class Key, class T, class Compare =less<Key> ,
class Allocator = allocator<pair<const Key, T>>>
class map;
typedef map< int , Edge* , less<int> > edgeMap;
typedef map< int , Node * , less<int> > nodeMap ;
ここで、Typedef は置き換え操作：
edgeMap inEdge;
は置き換えにより
map< int , Edge * , less<int> > inEdge;
を意味している。
ただし，edgeMap が型定義であると通知（多分？）
Edge
/* nodeとnodeとを接続する配線．srcNodeから
dstNodeへと方向を持っている有向枝である．
*/
class Edge{
Node* dstNode ;
Node* srcNode ;
public:
//Edgeの値 0,1,2； 2は不定値Xを示す．
/* シミュレーションでは0でも1でも無い値．
初期値として使用する．Xから0,1に変化する．
また，1,0の値が衝突するとXになる．
*/
int EIN;
Edge( ) { dstNode = srcNode =0; EIN=2;}
~Edge( ){ };
friend class Node; // Node, --- から
friend class ------ // privateにアクセス出来る
..…. ｝;
Node
必要なものは全て整理しておく．使う時に必要な物を
取り出して使用．メモリの節約とトレードオフの関係
にある．
class Node{
public:
int out; // 出力。初期値は不定 (2)
edgeMap inEdge; // 出力エッジのリスト
edgeMap outEdge; // 入力エッジのリスト
int
inEdgeCount;
bool
requestRun;
static simulation* SimObj;
Node( ):out(2), inEdgeCount(0),….,{ };
Node(Edge& o1, Edge& i1);
Node(Edge& o1, Edge &i1, &i2);
void outEdgeAdd( Edge& oE1){ ….,
outEdge.insert(edgeMap::value_type
(outEdgeCount++, &oE1)); }
virtual bool exec(int time, int svalue, Edge* e);
};
実際のmapの実装例(詳細：参考)
map <key, T, Compare, Allocator>
型 key のユニークなキーでインデックス付け、
型T の格納されている値へ高速にアクセス。
keyの比較に使うデフォルト演算： < 演算子
x ：キー，y：格納される値
pair<const key x, T y> value_type インスタンス
両方向性反復子
/* binaryTree を思いだそう */
テンプレート引数 key と型T
（t は T の値，u は T の const 値）。
????
コピーコンストラクタ T(t) と T(u)
デストラクタ
t.~T( )
アドレス &t と &u（それぞれ T* と const T* に対応）
代入
t = a（a はＴの値であり，定数の場合もある）
テンプレート引数 Compare で使う型は，二項関数の
必要条件を満足しなければならない。
map(詳細：参考)
template <class Key, class T,
class Compare = less<Key>
class Allocator = allocator<pair<const Key, T>> >
class map {
public:
typedef Key key_type;
typedef typename Allocator::pointer pointer;
//Allocatorは型(class)である
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
. . . . . . . . . .
. . . . . .
. . .
class iterator;
map(詳細：参考)
..............
.........
...
関数オブジェクトは，定義された関数を呼び出す演
算子（( ) 演算子）を持つ。
関数コードの先頭アドレスで示す．データー領域もあ
る．さらに，関数パラメータをつける．オブジェクト
でも良い．
class value_compare : public
binary_function<value_type, value_type, bool>
{
friend class map<Key, T, Compare, Allocator>;
protected :
Compare comp;
value_compare(Compare c): comp(c) {}
public :
bool operator( ) (const value_type&,
const value_type&) const;
};
コンストラクタ反復子(参考）
explicit map(
・・・・・・・・
const Compare& comp = Compare( ),
const Allocator& alloc = Allocator( ) );
comp を使ってキーを順序付ける（comp が与えられ
た場合）空のマップを構築する。このマップはアロ
ケータ alloc を使ってすべてのストレージ管理を行
う。
mapはbinaryTreeのnodeにallocで
pair<const Key, T> を割り付けていることを言っている．
map(tree）のノードを渡って移動するpointer（index)
がほしい．
map::iterator i；と宣言して，i++の様に表記し
て使いたい．
Iterator begin( );
マップ内に格納されている最初の要素を指す反復子
を返す。「最初」はマップの比較演算子 Compare
によって定義される。
iterator end();
マップ内に格納されている最後の要素（言い換えれ
ば，off-the-end 値）を指す反復子を返す。
シミュレータのコード
このmapを使って作成してある．
typedef map< int , Edge* , less<int> > edgeMap;
typedef map< int , Node * , less<int> > nodeMap ;
Net、 module, And
class net{
private:
int nodeCount; // net 内の Node の数
nodeMap node ; // net に属する Node
public:
net( )；
void addNode（Node* nodep);
}
// net クラスを module クラスという名前で利用するた
め。verilog 言語との対応
class module:public net{
public: module(){ motherNet = this; } };
class And: public Node{
public:
And(Edge& o1, Edge& i1, Edge& i2):
Node(o1,i1,i2, and){ }
// exec 関数のオーバーライド
bool exec(int time,int svalue, Edge* e);
};
Or, Not, input も同様
Andの実行部
bool And::exec(int time,int sv, Edge* e){
e->EIN = sv; // Pin の値をセット
out =1;
// 全ての Pin をスキャンするためのイテレータ
edgeMap::iterator eitr;
for ( eitr = inEdge.begin();
eitr != inEdge.end(); eitr++ )
{
// 入力に 2 が一つでもあれば,
if(eitr->second->EIN ==2 )
{
out = 2; break; // for 文を抜け出す ok?
}else if(pitr->second->EIN ==0 ){
// 入力に 0 が一つでもあれば,
out = 0; break; // for 文を抜け出す
}
}
// 基底クラス Nodeの exec 呼びだし
return( Node::exec( time, svalue, e ) );
}
Base class Nodeの実行部
And，Or, Not, 全ての素子が実行する
bool Node::exec(int time, int , Pin*) {
if(!requestRun){
requestRun = true;
SimObj->scheduleEvent(
new deliverEvent(time+1,this)); }
return( false ); // ok?
}
scheduleEvent
タイムスロット
exec
プログラム
タイムホイール
時刻
時刻
素子
素子
値
値
時刻
時刻
素子
素子
値
値
時刻
時刻
時刻
素子
素子
素子
値
値
値
時刻
時刻
時刻
素子
素子
素子
値
値
値
時刻
時刻
素子
素子
値
値
時刻
時刻
素子
素子
値
値
Simulation.h
信号変化イベントの定義
イベントのbase class
class event{
public:
unsigned int time ; // イベント発生時刻
simulation* SimObj;
event(unsigned int t): time(t){ }
// 純粋仮想関数
virtual void processEvent ()=0;
};
struct eventComparison{
bool operator () (event * left, event * right)
{ return left->time > right->time; }
};
( )があるから関数オブジェクト
実行イベント
派生イベント：
論理素子の実行による値変化のイベント
class execEvent : public event{
private:
Node* NodeObj; // イベント処理体操のNode
int svalue; // イベントによって伝搬される値
Edge* edge; // イベントが到達する edge
public: // コンストラクタ
execEvent( unsigned int time, int sv ,
Edge* e, Node* destNode ) :
event(time), NodeObj(destNode),
svalue(sv), edge(e) { }
void processEvent( ); // イベントの処理
};
Simulation class I
シミュレータのオブジェクト宣言
class simulation {
protected:
//優先順位キューの宣言
priority_queue <event *, vector<event *>,
eventComparison > eventQueue;
public:
unsigned int time;
unsigned int eventID; // イベントの ID
simulation* SimObj;
// コンストラクタ
simulation () : eventQueue(), time(0) ,
eventID(0) { SimObj = this; }
Simulation class II
// イベントの登録，値設定などシミュレーショ
ンで使う処理のインターフェース
void scheduleEvent (event * newEvent);
void set(int t, int v, Edge& e){
scheduleEvent(new
execEvent(t, v, &e, e.dstNode));
}
// 各時刻における論理値の計算
void run(unsigned int);
// 結果の伝搬
void deliver(unsigned int t, Node* nobj);
};
シミュレーションの実行部 I
void simulation::run(unsigned int cTime)
{
// 優先順位キューに登録されたイベントを
スキャン
while( !eventQueue.empty())
{
event * nextEvent = eventQueue.top();
time=nextEvent->time;
if( time >= cTime ) break; // while 文
を抜ける
nextEvent->processEvent(); // process
を実行
// 次のイベントを取り出す (ポップする)
eventQueue.pop();
delete nextEvent;
}
}
シミュレーションの実行部 I-2
（註）このeventQueue では異なる時刻の
eventはqueueされるが，同じ時刻のevent
はstackされている．
したがって，同時刻のイベントを取り出し
て実行すると，順序が逆になってしまう．
STLのmap：同じKeyの時には，積む順序の
区別まで必要のない問題を想定して作っ
てある．
シミュレーションの実行部 II
void simulation::scheduleEvent (event *
newEvent){
newEvent->SimObj = SimObj;
// イベントを優先順位キューへ登録
eventQueue.push ( newEvent);
}
//純粋仮想関数の実装
void execEvent::processEvent( ){
NodeObj->exec(time, svalue, pin );
}
－同時刻イベントの順序の問題－
// priority_queue <event *, vector<event *>,
eventComparison > eventQueue への単
純なpushではうまくいかない．
シミュレーションの実行部 II-2
不具合点の解決法
(1) ｓｔａｃｋされないようなqueue を作る．i.e.，
同時刻でもqueue動作をするように
eventQueue をつくる．
(2) 取り出し方を工夫する．
(3) queueへの積み方を工夫する．
(4) 時間の他に順序付けの変数を加える．た
とえば，同時刻のeventでもeventID で順
番をつけて，eventQueue につむ．
など，色々ある．
どれが，早いかとか，簡単かで選択する．
このsimulatorコードの記述と動作
int main(void){
simulation sim;
Node::SimObj = &sim;
//回路ネットの生成 module クラス (net クラスの別名)
のインスタンス
module test1;
Edge i1, i2, i3;
･････
NullNode null1(o1, i1);
･････
And and1( o4, o1, o2 );
･････
sim.set(0, 0, i1);
･････
for(int time=0; time< 100; time++) {
sim.run(time);
}
0.0 Gate constructorはnetに登録する．
同時にgate間の接続も行う．
0.1 シミュレータを生成して，対象をシミュ
レータに教える．
イベントが処理されると新たなイベントが
発生する。
• Run（）→ exec()
1. そのイベントを登録して処理する。
• Deriver（）
2. これを繰り返してイベントが無くなるまで続
ける。
3. 最初はイベントを登録しなければならない。
4. eventSet（）関数が必要。
試験：７/27（金）
１. 試験は授業内容全般とする．
２. 最終レポート締切りは8月3日（金）14時と
する．5号館509号室田向まで提出の事．
３．単位取得を望むものは，試験，最終レ
ポートの両方が必要．
４．最終レポートについては，いつでも質問
に来ること．TAが対応する予定．
まとめ
1. C++，オブジェクト，OOPによる作成法を
説明．
2. 代表的なデータ構造，list，stack，queue,
binaryTreeを作成し使い方を説明した．
3. しかし，アルゴリズムは時間不足，今後勉
強してほしい．
4. Cでも作れる．けれどC++．それとも，
Java，C#？ Lisp，prologもある．さらに，
systemC，specC， verilog, VHDLなど
もある．
5. programのcoding，systemのdesign？
複雑な物を簡単に作る技術？
複雑なシステムはそれでも複雑？
その設計をどう評価する．
あるいは，どう評価される？
•
今後のシステムはハードとソフトとがさら
に，複雑に入り組んでいる．それが設計
出来ないと，製造技術だけがあっても何
も作れない．

Download Report