読者です 読者をやめる 読者になる 読者になる

NSLで一斉射撃問題

一斉射撃問題の一次元セルラーオートマトンをNSLで作ってみました。
一斉射撃問題自体についてはWikipediawikipedia:en:Firing_squad_synchronization_problem)を見てください。

{m55_changebracket|`${'|`}$'}${m55_dnl}$
${m55_changepre|@}$${m55_dnl}$
declare Cell_Sentinel {
  output o[4];
}

declare Cell_General {
  input lft[4], rgt[4];
  output o[4];
}

declare Cell_Soldier {
  input lft[4], rgt[4];
  output o[4];
}

declare Squad simulation {
}

module Cell_Sentinel {
  o = 0x0;
}
${m55_define|state_change|`any {
    0b1 : o = r;
    (r == 0x1) : alt {
      (((lft == 0xc) | (lft == 0xd)) & ((rgt == 0xc) | (rgt == 0xd))) : {
        r := 0xd;
      }
      ((lft == 0x2) | (lft == 0xc)) : {
        r := if (rgt == 0x0) 0xc else 0x2;
      }
      ((rgt == 0x7) | (rgt == 0xc)) : {
        r := 0x7;
      }
    }
    (r == 0x2) : alt {
      ((lft == 0x5) & (rgt == 0x6)) : {
        r := 0xc;
      }
      ((rgt == 0x6) | (rgt == 0xd)) : {
        r := 0x6;
      }
      ((lft == 0x0) | (lft == 0x5) | (lft == 0xd)) : {
        r := 0x3;
      }
    }
    (r == 0x3) : {
      r := 0x4;
    }
    (r == 0x4) : {
      r := if (rgt == 0x6) 0xc else 0x5;
    }
    (r == 0x5) : {
      r := if (lft == 0x0) 0xd else 0x1;
    }
    (r == 0x6) : {
      r := if (lft == 0x4) 0xc else 0x1;
    }
    (r == 0x7) : alt {
      ((lft == 0xb) & (rgt == 0xa)) : {
        r := 0xc;
      }
      ((lft == 0xb) | (lft == 0xd)) : {
        r := 0xb;
      }
      ((rgt == 0xa) | (rgt == 0xd)) : {
        r := 0x8;
      }
    }
    (r == 0x8) : {
      r := 0x9;
    }
    (r == 0x9) : {
      r := if (lft == 0xb) 0xc else 0xa;
    }
    (r == 0xa) : {
      r := 0x1;
    }
    (r == 0xb) : {
      r := if (rgt == 0x9) 0xc else 0x1;
    }
    (r == 0xc) : {
      r := 0xd;
    }
    (r == 0xd) : any {
      (((lft == 0x0) | (lft == 0xd)) & ((rgt == 0x0) | (rgt == 0xd))) : {
        r := 0xf;
      }
    }
  }
'}$
module Cell_General {
  reg r[4] = 0x2;
  ${state_change}$${m55_dnl}$
}

module Cell_Soldier {
  reg r[4] = 0x1;
  ${state_change}$${m55_dnl}$
}
${m55_define|WIDTH|18}$
${m55_define|dsp1|`${m55_ifelse|@1|0||`%x${dsp1|${m55_expr|@1-1}$}$'}$'}$
${m55_define|dsp2|`${m55_ifelse|@1|1||`, sol[${m55_expr|${WIDTH}$-@1}$].o${dsp2|${m55_expr|@1-1}$}$'}$'}$
module Squad {
  Cell_Sentinel s_lft, s_rgt;
  Cell_General gen;
  Cell_Soldier sol[${m55_expr|${WIDTH}$-1}$];

  reg init = 0b1;

  integer i;

  {
    gen.lft = s_lft.o; gen.rgt = sol[0].o;
    sol[0].lft = gen.o; sol[0].rgt = sol[1].o;
    generate (i = 1; i < ${WIDTH}$-2; i++) {
      sol[i].lft = sol[i-1].o; sol[i].rgt = sol[i+1].o;
    }
    sol[${WIDTH}$-2].lft = sol[${WIDTH}$-3].o; sol[${WIDTH}$-2].rgt = s_rgt.o;

    init := 0b0;

    any {
      init : _monitor("${dsp1|${WIDTH}$}$", gen.o${dsp2|${WIDTH}$}$);
      (sol[0].o == 0xf) : _finish;
    }
  }
}

NSL処理系(NSL Core)に掛ける前に、拙作のマクロプロセッサmacr055(m55)を通す必要があります。もし動かしてみようという方がおられましたら、そちらも入手してください( https://github.com/metanest/macr055 )。awk等も必要になります。
参考のために Makefile も示します。

NSL_HOME=${HOME}/NSL

RM=/bin/rm
IVERILOG=/usr/local/bin/iverilog
VVP=/usr/local/bin/vvp
NSL=${NSL_HOME}/linux/i386/nslc.exe
M55=./m55

Squad.vcd: fssp.vvp
	${VVP} fssp.vvp

fssp.vvp: fssp.vl
	${IVERILOG} -o fssp.vvp fssp.vl

fssp.vl: fssp.nsl
	${NSL} -f fssp.nsl -o fssp.vl -verisim2 -target Squad -sim || ( status=$$?; ${RM} fssp.vl; exit $$status )

fssp.nsl: fssp_nsl.m5
	${M55} fssp_nsl.m5 > fssp.nsl || ( status=$$?; ${RM} fssp.nsl; exit $$status )

clean:
	${RM} -f fssp.nsl fssp.vl fssp.vvp Squad.vcd

make を実行すると、

$ make
./m55 fssp_nsl.m5 > fssp.nsl || ( status=$?; /bin/rm fssp.nsl; exit $status )
/home/ksmakoto/NSL/linux/i386/nslc.exe -f fssp.nsl -o fssp.vl -verisim2 -target Squad -sim || ( status=$?; /bin/rm fssp.vl; exit $status )
NSL CORE (version=20140505)
 Copyright (c) 2002-2014 IP ARCH, Inc. Naohiko Shimizu
 All rights reserved.
No License file found
Licensed to evaluation user without license file.
You are allowed to compile up to 2000 lines or statements
 You are limited EVALUATION USER


/usr/local/bin/iverilog -o fssp.vvp fssp.vl
/usr/local/bin/vvp fssp.vvp
VCD info: dumpfile Squad.vcd opened for output.
211111111111111111
321111111111111111
422111111111111111
522211111111111111
d32221111111111111
...
d1b77911dd1142261d
d11b7a11dd1152611d
d111c111dd111c111d
d117d211dd117d211d
d178d321dd178d321d
d779d422dd779d422d
db7ad526ddb7ad526d
d1c1d1c1dd1c1d1c1d
dddddddddddddddddd
ffffffffffffffffff

のようになります。