Date: Sun, 30 Jun 91 12:20:18 +0300 From: Yaron Keren Subject: Compute Maximal Compatibility Classes After computing MCCs myself two times (with lots of errors) I decided that my HP48SX will do it better. So here it is: This is a program for computing Maximal Compatibility Classes or MCCs. MCCs are being used when trying to minimize microinstruction size in microprogramming. The first step (and the hardest , most error-prune) in solving this problem is determining the MCCs. This program will automate the process. If you want to know more read: John P. Hayes, Computer Architecture and Organization Section 4.3.2 "Minimizing Microinstruction Size" (1st ed-pp. 281) or Agerwala T.:"Microprogram Optimization: A Survey", IEEE Trans. Comput., vol. C-25, pp. 962-973, October 1976 How to use the program ====================== Download the MCCs directory to your HP48SX. Changedir into. Press CST. To enter microinstructions Press INS. The INS procedure will ask you for the microinstructions. After each microinstruction press ENTER. When done press ENTER alone. Example: ======= microinstruction | Control Lines =================+============== I1 | a,b,c,g I2 | a,c,e,h I3 | a,d,f I4 | b,c,f INS ABCG ENTER ACEH ENTER ADF ENTER BCF ENTER ENTER The program assumes control lines names of A,B,C,D,... To let the program know the highest letter in control lines use INIS. Example: ======== We see that the instructions contains A..H therefore: INIS H ENTER To get the MCCs press NEXS repeatedly until you get a group containing no *-marked (The * marker means deleted) This group is the last group as the next group is empty. Example: ======== NEXS ( 30-120 seconds ) 1:{ "A" "*B" "*C" "*D" "*E" "*F" "*G" "*H" } NEXS ( 30-120 seconds ) 2:{ "A" "*B" "*C" "*D" "*E" "*F" "*G" "*H" } 1:{ "*BD" "*BE" "*BH" "CD" "*DE" "*DG" "*DH" "*EF" "*EG" "*FG" "*FH" "*GH" } NEXS ( 30-120 seconds ) 3:{ "A" "*B" "*C" "*D" "*E" "*F" "*G" "*H" } 2:{ "*BD" "*BE" "*BH" "CD" "*DE" "*DG" "*DH" "*EF" "*EG" "*FG" "*FH" "*GH" } 1:{ "BDE" "BDH" "DEG" "DGH" "EFG" "FGH" } Since no one *-marked in this group we finished. Now we have: S1: a ,*b,*c,*d,*e,*f,*g,*h S2: *bd,*be,*bh, cd ,*de,*dg,*dh,*ef,*eg,*fg,*fh,*gh S3: bde,bdh,deg,dgh,fgh S4: (empty) *-marked is deleted The MCCs are: a,cd,bde,bdh,deg,dgh,fgh Program directory follows... -------------------------------CUT------------------------------------------- %%HP: T(3)A(D)F(.); DIR INS \<< 1 \-> I \<< { } WHILE "I" I + " ENTER TO QUIT" + { \Ga } INPUT DUP "" \=/ REPEAT + 'I' INCR DROP END DROP DUP DUP SIZE 'LINS' STO 'SINS' STO LG2S 'GINS' STO \>> \>> INIS \<< "LAST LETTER" { \Ga } INPUT { } SWAP NUM 65 SWAP FOR I I CHR + NEXT DUP 'SI' STO LG2S 'GI' STO \>> NEXS \<< 64 STWS NEWG SI OBJ\-> 1 \-> L M \<< WHILE M L \<= REPEAT L ROLL USED M GET IF THEN "*" SWAP + END 'M' INCR DROP END L \->LIST \>> SO 'SI' STO GO 'GI' STO \>> SI { } USED [ 0 0 0 0 0 0 ] SO { } SINS { "ABCG" "ACEH" "ADF" "BCF" } GINS { # 47h # 95h # 29h # 26h } LINS 4 G16 { # 8000h # 4000h # 2000h # 1000h # 800h # 400h # 200h # 100h # 80h # 40h # 20h # 10h # 8h # 4h # 2h # 1h # 0h } GI { } GO { } CST { INS INIS NEXS } NEWG \<< SI SIZE \-> Z \<< Z 1 \->LIST 0 CON 'USED' STO { } 'GO' STO 1 Z 1 - FOR I I 1 + Z FOR J GI I GET GI J GET OR IF NEW THEN IF LEGAL THEN 'GO' SWAP STO+ 1 ELSE 0 END ELSE DROP 1 END IF THEN 'USED' I 1 PUT 'USED' J 1 PUT END NEXT NEXT GO LG2S 'SO' STO \>> \>> LEGAL \<< \-> V \<< GINS OBJ\-> DROP IFERR 1 LINS FOR I V AND G16 SWAP POS IF NOT THEN LINS I - DROPN 0 INV END NEXT THEN ELSE V 1 END \>> \>> NEW \<< DUP GO SWAP POS NOT \>> LG2S \<< OBJ\-> 1 \-> L M \<< WHILE M L \<= REPEAT L ROLL G2S 'M' INCR DROP END L \->LIST \>> \>> G2S \<< DUP TYPE CASE DUP 10 SAME THEN DROP "" 65 \-> S C \<< WHILE DUP 0 R\->B \=/ REPEAT DUP IF 1 R\->B AND B\->R THEN 'S' C CHR STO+ END SR 1 'C' STO+ END DROP S \>> END DUP 2 SAME THEN DROP \-> S \<< 0 1 S SIZE FOR I S I I SUB NUM 65 - 2 SWAP ^ + NEXT R\->B \>> END END \>> END -------------------------------CUT-------------------------------------------