6개의 레지스터를 가진 16bit 머신이 있습니다. 이 머신은 8종류의 명령을 받는다고 합니다.
모든 명령어는 fetch-decode-execute의 3 cycle을 소비합니다. 이 때 순차적으로 수행될 수 있는 명령어에 대해 pipelining을 한답니다.
문제에 정의된 방식대로 pipelining을 충실히 수행한다고 가정할 때, 어떤 프로그램이 끝났을 때 그 프로그램이 총 몇 cycle동안 수행되었는지를 출력하는 문제입니다. 의외로 단순한 문제입니다만 문제가 길어서, 아니면 이런 형태의 프로그래밍에 익숙지 않아서인지 Accepted 된 해답은 8개로 I번에 이어 2번째로 적었네요.
[spoiler="[풀이 보기]"] processor의 pipelining에 대해서는 Computer Architecture 과목에서 주로 다룹니다만, 여기서 이야기하는 pipelining은 가장 기초적인 수준입니다:
어떤 명령어 A 다음에 명령어 B가 있어, A가 수행된 후 반드시 명령어 B가 수행되는 형태라면, B는 pipelining되어 A가 decode될 때 B가 fetch됩니다.
위 조건에 맞지 않는 명령어 A는 무엇일까요? 문제에 설명되어 있듯이 레지스터의 값을 보고 '분기' 하는 cond나 loop명령이나, loop의 처음으로 돌아가는 pool명령입니다. 여기까지 확인했으면 뭔가 미심쩍긴 하지만 그냥 프로그램을 읽어들여(parsing) 돌려보면(interpreting) 되겠다-는 느낌이 옵니다. 돌려보며 다음 명령어가 pipelining될 수 있으면 1을, 그렇지 않으면 3을 cycle에 계속 더해나가면 되기 때문이죠. 물론 마지막 instruction은 끝까지 수행해야하는 점만 유의해서요. 어라? 문제를 마저 읽어보니 '케이스 중에 무한 loop이 포함된 것은 없다' 라고 나와있네요? 이 순간 미심쩍은 마음도 날아가버리고 그냥 프로그램의 실행기를 작성하는 문제로 굳혀집니다 만세 ~(-_-)~
(문제에 제시된 예제에 얼핏 무한 loop이 있는 게 보이지만 그건 레지스터 overflow로 바로 끝나는 케이스인 걸 알 수 있습니다)
무한 loop이 있다면 이 문제는 '풀기 불가능'한 문제가 되어버립니다. 그 이유는 유한 시간에 cycle이 무한한지 아닌지를 판단해야 하는데, 이 자체가 이미 halting problem이기 때문입니다 ^^
자 이제, 무언가 코딩양이 많고 복잡할 것 같은 실행기 작성을 어떻게 하면 빠른 시간에 오류 없이 짤까-하는 구현 문제가 남아버렸습니다. 수행속도를 위해 instruction을 하나의 구조체로 표현해서 프로그램을 파싱한 후 instruction의 집합을 가지고 수행을 합시다.
분기(cond나 loop)같은 경우, dnoc / pool을 만나기 전까지는 그 분기점이 어디로 될지 모릅니다. 이 때엔 괄호 매칭하듯이 stack을 사용해서 괄호가 닫힐 때(dnoc / pool) 여는 부분에 분기 목표를적어주면 되겠죠.
[/spoiler]
[spoiler="[코드 보기]"]아래는 간단하게 switch를 사용하여 만들어본 C++ 해답 예제입니다. 반복되는 동작은 매크로로 정의해서 코딩속도를 높이고 실수를 줄이려고 노력해보았습니다. 조금 어려운 것이 명령어에서 value가 들어오는 부분 처리인데, 여기에 직접 값이 올 수도 있고 레지스터가 올 수도 있어 이를 하나로 인코딩할지 아니면 두 개로 나누어서 처리를 할지, 아니면 아예 instruction의 종류를 나누어(LOADI / LOADR같이) 처리할지 난감했는데, 그냥 어차피 값의 범위는 16bit 안이라 매우 큰 값을 두고 그 값을 기준으로 값이냐/레지스터 번호냐를 판가름하게 해서 하나의 val 필드로 인코딩했습니다. cond/loop/pool 명령에 필요한 분기 목적점도 val 필드에 집어넣게 하고 마지막으로 bit field를 사용해 instruction 구조체 크기를 8byte로 맞추었습니다 :$
~~~ cpp
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define BIGVAL 1048576
#define OP_REG (program[pc].reg)
#define OP_VAL (program[pc].val)
#define value(v) ((v) >= BIGVAL ? reg[(v) - BIGVAL] : (v))
#define check_overflow(v) \
do { \
if ((v) < -32768 || (v) > 32767) \
return -1; \
} while(0)
#define pipeline_accumulate() \
do { \
ret++; \
pipelined = true; \
} while(0)
#define pipeline_clear() \
do { \
ret += 3; \
pipelined = false; \
} while(0)
typedef enum {
LOAD, STORE, MOVE, ADD, SUB, LOOP, POOL, COND, END
} op_t;
struct instr {
op_t opcode : 16;
int reg : 16;
int val;
};
int interpret(const vector<instr> &program)
{
register int ret = 0;
register int m = 0;
register int pc = 0;
int reg[6] = {0};
bool pipelined = false;
while(true) {
switch(program[pc].opcode) {
case LOAD:
reg[OP_REG] = m;
pipeline_accumulate();
pc++;
break;
case STORE:
m = value(OP_VAL);
pipeline_accumulate();
pc++;
break;
case MOVE:
reg[OP_REG] = value(OP_VAL);
pipeline_accumulate();
pc++;
break;
case ADD:
reg[OP_REG] += value(OP_VAL);
check_overflow(reg[OP_REG]);
pipeline_accumulate();
pc++;
break;
case SUB:
reg[OP_REG] -= value(OP_VAL);
check_overflow(reg[OP_REG]);
pipeline_accumulate();
pc++;
break;
case LOOP:
if (reg[OP_REG] > 0) pc++;
else pc = program[pc].val;
pipeline_clear();
break;
case POOL:
pc = program[pc].val;
pipeline_clear();
break;
case COND:
if (reg[OP_REG] > 0) pc++;
else pc = program[pc].val;
pipeline_clear();
break;
case END:
return pipelined ? ret + 2 : ret;
default:
break;
}
}
}
inline int parse_reg()
{
string token;
cin >> token;
return token[1] - '0';
}
inline int parse_val()
{
string token;
cin >> token;
if (token[0] == 'R')
return token[1] - '0' + BIGVAL;
else
return atoi(token.c_str());
}
void solve()
{
int n;
int p = 0;
vector<instr> program;
stack<int> stk_cond;
stack<int> stk_loop;
instr inst;
cin >> n;
while(n--) {
memset(&inst, 0, sizeof(inst));
string token;
cin >> token;
if (token == "dnoc") {
program[stk_cond.top()].val = p;
stk_cond.pop();
continue;
}
if (token == "load") {
inst.opcode = LOAD;
inst.reg = parse_reg();
}
else if (token == "store") {
inst.opcode = STORE;
inst.val = parse_val();
}
else if (token == "move") {
inst.opcode = MOVE;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "add") {
inst.opcode = ADD;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "sub") {
inst.opcode = SUB;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "loop") {
inst.opcode = LOOP;
stk_loop.push(p);
inst.reg = parse_reg();
}
else if (token == "pool") {
inst.opcode = POOL;
inst.val = stk_loop.top();
program[stk_loop.top()].val = p + 1;
stk_loop.pop();
}
else if (token == "cond") {
inst.opcode = COND;
inst.reg = parse_reg();
stk_cond.push(p);
}
program.push_back(inst);
p++;
}
memset(&inst, 0, sizeof(inst));
inst.opcode = END;
program.push_back(inst);
int result = interpret(program);
if (result == -1)
cout << "error" << endl;
else
cout << result << endl;
}
int main(void)
{
int tests;
cin >> tests;
while(tests--)
solve();
}
~~~
[/spoiler]
[spoiler="[조금 더 알고 싶다면]"]아래는 좀 더 복잡하게 만들어본 C++ 예제입니다. 복잡하다곤 하지만 위의 간단하다는 코드와 다른 부분은 interpret 함수 구조밖에 없습니다 :$
~~~ cpp
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define BIGVAL 1048576
#define OP_REG (program[pc].reg)
#define OP_VAL (program[pc].val)
#define value(v) ((v) >= BIGVAL ? reg[(v) - BIGVAL] : (v))
#define check_overflow(v) \
do { \
if ((v) < -32768 || (v) > 32767) \
return -1; \
} while(0)
#define pipeline_accumulate() \
do { \
ret++; \
pipelined = true; \
} while(0)
#define pipeline_clear() \
do { \
ret += 3; \
pipelined = false; \
} while(0)
typedef enum {
LOAD, STORE, MOVE, ADD, SUB, LOOP, POOL, COND, END
} op_t;
struct instr {
op_t opcode : 16;
int reg : 16;
int val;
};
int interpret(const vector<instr> &program)
{
register int ret = 0;
register int m = 0;
register int pc = 0;
int reg[6] = {0};
bool pipelined = false;
#ifdef __GNUC__
void *label[] = {&&load, &&store, &&move, &&add, &&sub, &&loop, &&pool,
&&cond, &&end};
#define fetch() goto *label[program[pc].opcode]
#else
#define fetch() \
do { \
switch (program[pc].opcode) { \
case LOAD: goto load; \
case STORE: goto store; \
case MOVE: goto move; \
case ADD: goto add; \
case SUB: goto sub; \
case LOOP: goto loop; \
case POOL: goto pool; \
case COND: goto cond; \
case END: goto end; \
default: return -1; \
} \
} while(0)
#endif
fetch();
load:
reg[OP_REG] = m;
pipeline_accumulate();
pc++;
fetch();
store:
m = value(OP_VAL);
pipeline_accumulate();
pc++;
fetch();
move:
reg[OP_REG] = value(OP_VAL);
pipeline_accumulate();
pc++;
fetch();
add:
reg[OP_REG] += value(OP_VAL);
check_overflow(reg[OP_REG]);
pipeline_accumulate();
pc++;
fetch();
sub:
reg[OP_REG] -= value(OP_VAL);
check_overflow(reg[OP_REG]);
pipeline_accumulate();
pc++;
fetch();
loop:
if (reg[OP_REG] > 0) pc++;
else pc = program[pc].val;
pipeline_clear();
fetch();
pool:
pc = program[pc].val;
pipeline_clear();
fetch();
cond:
if (reg[OP_REG] > 0) pc++;
else pc = program[pc].val;
pipeline_clear();
fetch();
end:
return pipelined ? ret + 2 : ret;
}
inline int parse_reg()
{
string token;
cin >> token;
return token[1] - '0';
}
inline int parse_val()
{
string token;
cin >> token;
if (token[0] == 'R')
return token[1] - '0' + BIGVAL;
else
return atoi(token.c_str());
}
void solve()
{
int n;
int p = 0;
vector<instr> program;
stack<int> stk_cond;
stack<int> stk_loop;
instr inst;
cin >> n;
while(n--) {
memset(&inst, 0, sizeof(inst));
string token;
cin >> token;
if (token == "dnoc") {
program[stk_cond.top()].val = p;
stk_cond.pop();
continue;
}
if (token == "load") {
inst.opcode = LOAD;
inst.reg = parse_reg();
}
else if (token == "store") {
inst.opcode = STORE;
inst.val = parse_val();
}
else if (token == "move") {
inst.opcode = MOVE;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "add") {
inst.opcode = ADD;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "sub") {
inst.opcode = SUB;
inst.reg = parse_reg();
inst.val = parse_val();
}
else if (token == "loop") {
inst.opcode = LOOP;
stk_loop.push(p);
inst.reg = parse_reg();
}
else if (token == "pool") {
inst.opcode = POOL;
inst.val = stk_loop.top();
program[stk_loop.top()].val = p + 1;
stk_loop.pop();
}
else if (token == "cond") {
inst.opcode = COND;
inst.reg = parse_reg();
stk_cond.push(p);
}
program.push_back(inst);
p++;
}
memset(&inst, 0, sizeof(inst));
inst.opcode = END;
program.push_back(inst);
int result = interpret(program);
if (result == -1)
cout << "error" << endl;
else
cout << result << endl;
}
int main(void)
{
int tests;
cin >> tests;
while(tests--)
solve();
}
~~~
혹시 컴퓨터구조를 공부해서 아시는 분들도 있겠지만, 이 문제와는 달리 실제 요즘 머신에서는 분기가 있다고 해서 pipelining을 아예 안하지 않습니다 : 분기 예측(branch prediction)이라고 해서, 어느 분기로 간다고 가정하고 미리 pipelining을 해버립니다. 물론 이 때 잘못 예측할 가능성이 분명 있기 때문에 그 경우 pipeline을 비워주고-_- 다시 채워야하는 문제가 있습니다. 거기에 switch같이 address table을 사용해서 간접 jump(jump할 목적 address가 변수인 형태)를 하는 경우에는 branch target buffer라는 개념을 추가로 사용합니다.
위 복잡한 코드는 그런 branch target buffer misprediction을 줄이기 위한 최적화가 포함되었습니다. branch 지점을 늘려서 입력 코드가 부분적으로 일정한 패턴으로 수행되는 경우에 그 효율을 높이기 위한 것이죠. 거기에 더해 gcc에서 컴파일할 경우에는 gcc extension인 label as value를 사용하도록 했습니다. 이론적으로도 실제로도 단일 무한 loop switch에 비해 더 빠릅니다만 josh님께 소스를 보내 검증을 부탁드렸더니 수행속도면에서는 큰 차이를 못 느꼈다고 하시네요. 아마 코드를 interpreting하는 부분에 걸리는 시간 자체가 애초에 크지 않은 것 같습니다. 결국 뻘짓이 되어버렸는데 그냥 제가 요즘 하는 일에 연관되어 있다보니 아는 체 좀 하려고 써보았습니다 :)
branch target buffer misprediction에 대한 링크 몇 개 걸어둘게요. http://en.wikipedia.org/wiki/Branch_target_predictor http://www.complang.tuwien.ac.at/anton/lvas/sem06w/revucky.pdf
[/spoiler]
lazyboy
6개의 레지스터를 가진 16bit 머신이 있습니다. 이 머신은 8종류의 명령을 받는다고 합니다.
모든 명령어는 fetch-decode-execute의 3 cycle을 소비합니다. 이 때 순차적으로 수행될 수 있는 명령어에 대해 pipelining을 한답니다.
문제에 정의된 방식대로 pipelining을 충실히 수행한다고 가정할 때, 어떤 프로그램이 끝났을 때 그 프로그램이 총 몇 cycle동안 수행되었는지를 출력하는 문제입니다. 의외로 단순한 문제입니다만 문제가 길어서, 아니면 이런 형태의 프로그래밍에 익숙지 않아서인지 Accepted 된 해답은 8개로 I번에 이어 2번째로 적었네요.
[spoiler="[풀이 보기]"] processor의 pipelining에 대해서는 Computer Architecture 과목에서 주로 다룹니다만, 여기서 이야기하는 pipelining은 가장 기초적인 수준입니다:
어떤 명령어 A 다음에 명령어 B가 있어, A가 수행된 후 반드시 명령어 B가 수행되는 형태라면, B는 pipelining되어 A가 decode될 때 B가 fetch됩니다.
위 조건에 맞지 않는 명령어 A는 무엇일까요? 문제에 설명되어 있듯이 레지스터의 값을 보고 '분기' 하는 cond나 loop명령이나, loop의 처음으로 돌아가는 pool명령입니다. 여기까지 확인했으면 뭔가 미심쩍긴 하지만 그냥 프로그램을 읽어들여(parsing) 돌려보면(interpreting) 되겠다-는 느낌이 옵니다. 돌려보며 다음 명령어가 pipelining될 수 있으면 1을, 그렇지 않으면 3을 cycle에 계속 더해나가면 되기 때문이죠. 물론 마지막 instruction은 끝까지 수행해야하는 점만 유의해서요. 어라? 문제를 마저 읽어보니 '케이스 중에 무한 loop이 포함된 것은 없다' 라고 나와있네요? 이 순간 미심쩍은 마음도 날아가버리고 그냥 프로그램의 실행기를 작성하는 문제로 굳혀집니다 만세 ~(-_-)~
(문제에 제시된 예제에 얼핏 무한 loop이 있는 게 보이지만 그건 레지스터 overflow로 바로 끝나는 케이스인 걸 알 수 있습니다)
무한 loop이 있다면 이 문제는 '풀기 불가능'한 문제가 되어버립니다. 그 이유는 유한 시간에 cycle이 무한한지 아닌지를 판단해야 하는데, 이 자체가 이미 halting problem이기 때문입니다 ^^
자 이제, 무언가 코딩양이 많고 복잡할 것 같은 실행기 작성을 어떻게 하면 빠른 시간에 오류 없이 짤까-하는 구현 문제가 남아버렸습니다. 수행속도를 위해 instruction을 하나의 구조체로 표현해서 프로그램을 파싱한 후 instruction의 집합을 가지고 수행을 합시다.
분기(cond나 loop)같은 경우, dnoc / pool을 만나기 전까지는 그 분기점이 어디로 될지 모릅니다. 이 때엔 괄호 매칭하듯이 stack을 사용해서 괄호가 닫힐 때(dnoc / pool) 여는 부분에 분기 목표를적어주면 되겠죠.
[/spoiler]
[spoiler="[코드 보기]"]아래는 간단하게 switch를 사용하여 만들어본 C++ 해답 예제입니다. 반복되는 동작은 매크로로 정의해서 코딩속도를 높이고 실수를 줄이려고 노력해보았습니다. 조금 어려운 것이 명령어에서 value가 들어오는 부분 처리인데, 여기에 직접 값이 올 수도 있고 레지스터가 올 수도 있어 이를 하나로 인코딩할지 아니면 두 개로 나누어서 처리를 할지, 아니면 아예 instruction의 종류를 나누어(LOADI / LOADR같이) 처리할지 난감했는데, 그냥 어차피 값의 범위는 16bit 안이라 매우 큰 값을 두고 그 값을 기준으로 값이냐/레지스터 번호냐를 판가름하게 해서 하나의 val 필드로 인코딩했습니다. cond/loop/pool 명령에 필요한 분기 목적점도 val 필드에 집어넣게 하고 마지막으로 bit field를 사용해 instruction 구조체 크기를 8byte로 맞추었습니다 :$
혹시 컴퓨터구조를 공부해서 아시는 분들도 있겠지만, 이 문제와는 달리 실제 요즘 머신에서는 분기가 있다고 해서 pipelining을 아예 안하지 않습니다 : 분기 예측(branch prediction)이라고 해서, 어느 분기로 간다고 가정하고 미리 pipelining을 해버립니다. 물론 이 때 잘못 예측할 가능성이 분명 있기 때문에 그 경우 pipeline을 비워주고-_- 다시 채워야하는 문제가 있습니다. 거기에 switch같이 address table을 사용해서 간접 jump(jump할 목적 address가 변수인 형태)를 하는 경우에는 branch target buffer라는 개념을 추가로 사용합니다.
위 복잡한 코드는 그런 branch target buffer misprediction을 줄이기 위한 최적화가 포함되었습니다. branch 지점을 늘려서 입력 코드가 부분적으로 일정한 패턴으로 수행되는 경우에 그 효율을 높이기 위한 것이죠. 거기에 더해 gcc에서 컴파일할 경우에는 gcc extension인 label as value를 사용하도록 했습니다. 이론적으로도 실제로도 단일 무한 loop switch에 비해 더 빠릅니다만 josh님께 소스를 보내 검증을 부탁드렸더니 수행속도면에서는 큰 차이를 못 느꼈다고 하시네요. 아마 코드를 interpreting하는 부분에 걸리는 시간 자체가 애초에 크지 않은 것 같습니다. 결국 뻘짓이 되어버렸는데 그냥 제가 요즘 하는 일에 연관되어 있다보니 아는 체 좀 하려고 써보았습니다 :)
branch target buffer misprediction에 대한 링크 몇 개 걸어둘게요.
http://en.wikipedia.org/wiki/Branch_target_predictor
http://www.complang.tuwien.ac.at/anton/lvas/sem06w/revucky.pdf
[/spoiler]
16년 전