트리플에스보러 카이스트축제 놀러갔다가 엘마가서친구가사주는칵테일마시고 취했는데 기차에서 노트북으로 코드포스를 켜서 A번을 제출해버리는 실수를 한 후에 -104가 됨

A

생략

여담: 사실 2분만에 풀었는데 그때딱 기차가도착해서 기차타서 가방 치우고 노트북폈는데 와이파이연결개억까당해서 9분에제출함

B

대충 2개의 bucket을 만들어서, a[i]>a[i+1] 이면 a[i+1]에 k를 무조건 더해야만 하니까 k를 더하는 버킷으로 보내면될거같음 근데 예제가 안도는걸보니 반례가 있는듯

그뒤로 멀미나서 속이안좋아서 살짝 위기를 겪고 노트북덮고 20분정도잤음

.

B업솔빙

왜 못 풀었지 그냥 k를 max(지금까의 max값-a[i])로 고르고 앞에서부터 이 k가 되는지 안되는지를 확인하면 되는거아님?

귀찮아서 코드는나중에짬 (사실 정수론 과제해야됨)

C

다행히일어났더니더이상안토할것같아서 c를 봄 짝수면 나눠지고 홀수면 1을 더함

관찰1. 언젠가는 2^n 꼴에 수렴해서 1이 될거고 1→2→1→2→ ... 가 반복됨

관찰2. 그러면 이 경로에 있는 수 중에서 수에 도달하는 스텝수를 계산해서 n개에서 다 나타나면서 스텝수가 최소가 되는 걸 구하면 됨

관찰다했는데 최적화를 제대로 못해서 틀린게개아쉽다 아직 짬이더차야하는듯

.

C업솔빙

관찰1의 '사이클'에서 1로 끝나는 경우랑 2로 끝나는 경우를 나눠서 생각하면 되고

어차피 1 또는 2에서 시작하니까 사이클을 뒤집은다음에 그리디하게 모든 수가 만들어질 수 있을때까지 가면 됨 (페타쌤 풀이를좀참고했어요ㄱㅅㅎㄴㄷ)

예를 들어 예제의 [3, 6, 7, 16, 8, 8, 7]

3: 3 4 2 1 / cost 3, 7: 7 8 4 2 1 / cost 4

뒤집으면

1 2 4 3 6

1 2 4 8 7 이니까 4가 만들 수 있는 최선의 선택

공간이터지진않겠지? n 10^5 * path길이60 * 2 * 4bytes = 4.8*10^7 < 512*10^6 → ok 

AC

D 업솔빙 → 귀찮아서 나중에함

인생 첫 팀 ps 대회였다. 2023년에 도서관에서 PostechProgrammingContest의 포스터라는 것을 봤을 때는 와저런건정말고능한사람들만하는건가보다 하고 지나갔던 기억이 있는데 3년이 지나서 이걸 내가 나가네.

백준섭종이라는 대 자연재해가 터지면서 Equinox와 kyungdain이 정병을 쳐먹는 걸 실시간으로 관전할 수 있었는데 돔저지 세팅이 다행히 잘 된 것 같았고 전반적으로 순조롭게 진행되었다. 밑에도 쓰겠지만 다들 너무 수고 많았다...

뭔가 대회 전에는 망하면 멘헤라 와서 후기를 쓰기 힘들 것 같다고 생각했는데 막상 당해보니까 망한 대회가 할 말이 더 많다는 걸 깨달았다. 솔직히 저희 왜 망했는지 궁금하지않나요? 이하 뇌 빼고 씀

배경

동아리에 여자도 많이 없는데 내년에 여자인 친구들을 모아서 ppc 나가면 친해질 수 있겠지?
ㄴ 팀명 뭘로할거임?
ㄴ 미소녀즈(msnz)?
- cyan, POSCAT MT (2025.10)

이렇게해서 3명 전원 주민번호 뒷자리 4로 시작하는 BOJ 플레5의 꽤나 희귀한 팀이 결성되었다. 어 등차수열이네

여기서 알아야 할 **중요한** 사실은, 내가 스스로를 미소녀로 지칭한 게 아니라 내 팀명을 트리플에스 미소녀즈에서 따온 것이다...

간략한 팀원소개

lyj- 22학번, 나에게먼저ppc를같이나가자고제안해준멋선, 핸들이없어서본명초성임, 코드포스 경험 1회, 근데 대기업의 러브콜을 받은 코테의 신, 디엪에스와비엪에스의 능력자(포닉스는미로에갇혔다.어?살려줘!여기가어디지?<-주면잘먹음), 시안멘탈케어담당(아개망했어난왤케멍청하지하진짜어카지-아니야괜찮아!)

fixed- 25학번, 내년 포스캣 회장(예정), 컴퓨터 비전의 권위자, "난 ps가 싫어 이게재밌나", 시간복잡도같은거 잘모르겠다함, 근데 골드 DP슥슥풀어냄, 말만싫다하고 연습열심히함, 애니프사가 보증해주는 확실한 코딩 체급, 아스노요조라와 카라쿠리삐에로를 아주잘부름 

cyan- 23학번, 유일한 "ps러"(= 문제가풀릴때도파민을느끼며 ps하다가과제레이트를한적있고 코드포스티어정병이라는개념을이해함), 코포계정생성9개월차, 레이팅 1400, 2주 전 serin이못풀었던 딥2 D 컨스를 풀고서 주변의 기대를 한몸에받고있던상태(왜그랬지풀지말걸), azber라는 분이랑 무슨 사이인지는잘모르겟는데 밤에 디코로 영통하면서 그림판으로 문제풀이를 듣는다는 소문이있음...

놀랍게도 백준이 없어지기 전에 팀연습도 했다. 2번의 팀연습을 한 결과로 알게 된 건 골드를 다 풀고 내가 플레하위를 진짜 운좋게풀면 초고점이고 대충 머릿속으로 골드2 이하를 다 푸는 걸 목표로하자고 생각햇따. 그러나 정말 무서운 사실을 깨달았는데 팀연습 때 대학 대회 특성상 자주 등장하는 실버~골드하위의 게임이론과 컨스를 그 누구도 좋아하지않아서 결국 전부 다 내가 짬처리를 했고 같이 고민하도록 시켜보기도 했는데 결국엔 내가 풀었다(아무래도 코테에 잘 나오진 않긴 하죠). 개인적으로 스스로의 직관력이 쓰레기라고 생각하는데 그래도 내가 세 명 중에는 코드포스A,B를 가장많이풀어봤을것같긴해서어쩔수없다.... 또한 앞서 말했듯 내가 팀 내의 유일한 ps 경력자이기 때문에 웬만해서는 내가 버스를 운전해야 할 그림이었기 때문에 부담이 더 컸던 것 같다.

그래서 전날밤에 호달달 떨면서 최악의 시나리오를 상상한다.

lyj가 구현에서 절어서 디버깅하느라 한참을 헤맴, 그래서 내가 디버깅 도와주느라 다른문제들을 보지 못함, cyan이 긴장해서 뇌가굳어서 풀어야하는 쉬운컨스에서 아무런관찰도하지못하고 멘탈이터짐, 3시간쯤 지나서 드디어 fixed가 문제를 풀었는데 키보드를 뺏어오지 못해서 브론즈 두개 실버 하나 골드 한개 정도 풀고 끝나는 시나리오

근데곧알아보겠지만 정말이게거의 그대로 일어났다....

대회 전

대회가 시작하기에 앞서 각자 팀노트를 뽑아오기로 했다. 포스캣 동방 프린터의 사용 방법을 아는 사람이 나밖에없어서 보내주시면 뽑아주겠다고 했는데, fixed가 보내준 파일을 열어봤더니 다크모드로 되어 있어서 악플을 좀 달았다. 심지어 파이썬이야

각자 뽑은 팀노트는 '팀'노트라고 불러도되는지에 대해 깊생을 하다 보니 과방 안마의자에서 잠들었다. 그래서 헐레벌떡 제일 늦게 왔더니 친절하게 컴퓨터 앞 자리를 비워주셨길래 강제로 스타트를 끊게 되었다. 할 게 없어서 한컴타자연습을 하면서 긴장을 풀었다.

그리고 팀노트를 합쳐보니 25장 제한인데 26장이길래 잠시 소동이 있었는데, fixed가 표지를 버리면서 해결했다.

대회 중

대회를 망한 후에 정병이 와서 슼보 사진을 찍어두지 않았다. 따라서 대략적인 타임라인이다.

그리고 오픈콘 전에 슼보가 노출되어버려서 순서를 섞었다는데 이 후기는 오픈콘 전에 쓰여졌기 때문에 본대회 기준 번호임. 내가 주석으로 오픈콘 기준 번호도 적어뒀으니 참고바람

~0:10 A AC (+2)

일단 무지성으로 종이 더미를 반으로 갈라서 왼쪽에 있는 lyj에게 앞쪽 절반, 오른쪽에 있는 fixed에게 뒤쪽 절반을 던져주고 나는 템플릿을 짰다. 그리고 포스캣 사람들로 구성된 2퍼플 1블루팀, 1블루 1민트팀이 1,2등으로 유력한 상태여서 그 팀 위주로 보면 될 것이라 생각했다

lyj가 A번이 쉬워보인다고 던져주길래 봤더니 브론즈였고, 내가 풀었는데 너무 긴장해서 등호를 빼먹어서 틀린다. 그래서 어 뭐지...? 하고 lyj를 불러서 도와달라 해서 고쳤는데 또 틀려서 2WA를 받는 사건이 일어나버린다. (사실 여기서부터 말아먹었음을 직감했다) 다행히 고쳐서 맞았다.

이후 cyan은 C, D, lyj는 B? C? E? (사실 모르겠음), fixed는 I를 본다. 근데 I (=오와 열)는 개레전드로 어려운 문제였기 때문에 아무런 성과도 이루어지지 않았고 B (=Classical postech problem, cpppp 나오는 거) 우리 기준 어려운문제였다... 

일단 C (=POSTECH Programming Colosseum, 오픈콘 H) 트리라는 단어를 읽고 격자 bfs인가...? 하고 머리가 복잡해져서 그냥 넘겼던 것 같고 (좀만더자세히읽을걸) D (=부분수열의 개수, 오픈콘 J) 이상한 DP로 풀어보려다가 개삽질을 했다. 사실 일반적인 상태의 나

관찰 1. N범위를 보고 O(N log N)까지 돌 테니까 일단 정렬ㄱ?

관찰 2. 그러면 이웃한 것들의 관계를 어쩌고 저쩌고

정도의 사고는 가능했겠으나 이미 A를 두 번 틀리고 정신이 나가버렸다. so very classic Div2 B material로 느껴지는데 이걸 왜 못했지... 1시간이 지나도록 아무 성과도 없는데 막 3솔한 팀들도 많아서 정병이 왔다.

~1:00 J AC (=포스텍 도수체조, 오픈콘 K)

그러다가 J가 풀리고 있는 것 같은데 너무 고능해서 잘 모르겠다고 (보통 팀원들이 컨스 나한테 던질 때 쓰는 템플런임) fixed가 던져줬고 예제에 있는

1 5

5 7 

을 보고 역시 kwoncycle 선배님 이라고 생각했다.

보자마자 3분만에 J가 90% 정도 풀리는 관찰을 찾았다고 주장하며 캬역시나야 하면서 짜기 전에 팀원들에게 검증을 받으려고 했는데 설명하다 보니 내가 틀렸다는 걸 깨닫고 머쓱해졌다. 그래서 15?분 정도 더 관찰한 결과

관찰 1. 도미노를 만들 수만 있으면 무한복사가능

관찰 2. 대각선은 서로에게 닿을수없어...

생각 2-1. 이걸 어떻게 수식화하지? 택시거리가 홀수이면 닿을수있다

생각 2-2. 그러면 인덱스의 차이로 아하

로 풀이가 나왔고 구현도 내가 구체화했다. fixed랑 같이 화면을 보며 불안형 여친마냥 나 맞지? 이거 맞겠지?하며 검증하면서 짜서 AC.

~2:00

lyj가 옆에서 C(=오픈콘 H)는 달팽이 배열을 짜면 된다고 외쳤는데, 항상 2개인 경우만 되는지 확실하지 않아서 증명해야 할 것 같다면서 구현을 시작하지 못한 상태였다. 그러다가 일단 해 보겠다고 해서 키보드를 줘서 짜기 시작했는데 45분 넘게 못 짜고 헤맸다. 원래 멘탈이 터진 cyan에게 괜찮다는 말을 해주던 lyj가 멘탈이 완전히 터져버렸다. 그래서 내가 역으로 괜찮으니까 제발 멘탈 잡아달라고 하는 사태가 일어나버림

뭔가 이대로 뒀다가는 망할 것 같았고 C는 거의 모든 팀이 풀었기 때문에 내가 나서서 책임져야겠다고 생각했다. 나는 구현을 정말 정말 못하지만 그래도 고등학교 내신에서 달팽이 배열을 짜 본 적은 있었고, 다른 팀들도 다 풀었는데 내가 못할 게 뭐야? 라는 근거 없는 믿음이 있었다. 하지만 단순한 달팽이가 아니었고 따져야 할 조건들이 너무 많았다. 처음부터 lyj의 설명을 듣고 난 상태였어서 다른 모양을 떠올릴 생각조차 못했고 여기서 C를 다시 읽어보려는 시도라도 했더라면 좋았을 텐데 못해서 너무 아쉽다. 사실 모두가 풀었다는 말은 더 쉬운 풀이가 있다는 뜻이었을 거라는 오만한 생각이라도 했을걸.... 

대충 이 상황과 병렬적으로 fixed는 E(=포닉스의 학점은?, 오픈콘 D) 가 쉬운 것 같다면서 (실제로 거의 모든 팀이 풀었었음) 그냥 비교하면 되는 거 아님? 이라고 했는데 예제2가 왜 도는지 모르겠다고 나를 불렀다. 근데 일단 뭐가 수식이 너무 많고 지문도 너무 길고 비직관적이고 정말 읽기 싫게 생긴 문제였다. 예제를 읽고 설명시켜주는 데에는 성공했으나 뭘 하라는 건지 모르겠어서 멍을 좀 때렸다.

결국 E는 버리고, 내가 쉬지 않고 반례를 던지고 디버깅을 도와줘서 문제의 조건에 맞는 달팽이를 제대로 출력하는 데에 성공했다. 그런데도 WA를 받았다. 가능한 모든 상황에 대한 예제가 다 돌았고 이유를 전혀 알 수 없었다. lyj는 '답이 2개가 아닐 수 있나?'에 다시 빠져버렸고, fixed도 망했어요... 하면서 간헐적으로 멍을 때리기 시작했다.

그래도 lyj와 fixed가 힘을 합쳐서 E를 맞게 된다. 나는 지금도 문제 상황을 모르겠다. for, if, 부등호만으로 해결할 수 있는 브론즈라는데 아직도 문제를 이해하지 못했다. 진짜 저능해졌나??

이 쯤에서 내가 인터랙티브였던 H(=Classical Interactive Problem, 오픈콘 C)도 풀어보려고 시도했다. 사실 살면서 인터랙티브를 한 번도 풀어본 적은 없었지만, 예비소집 때 인터랙티브를 푸는 방법을 배웠고, (그냥 endl만 붙여주면 된다고 했다) 많이 어려워보이지 않아서 해 보려고 했다.

생각 1. 쿼리가 최대 2N개니까, N+N으로 구성해보자. 일단 차이 N개를 구하고...?

생각 2. 3개씩 해볼까? 그러면 대소관계를 알 수 있네? 

근데 너무 저능했던 나머지 이것만으로 확정이 된다는 생각을 못 해서 빙글빙글 돌기만 했다.

~3:00 C AC (=오픈콘 H)

이제 뭘 풀지...? 하고 돔저지에 다시 들어가봤다. 근데 클릭을 잘못해서 C의 WA 결과를 눌렀는데 warning:무슨뭐가 초기화가 안됐을수있음 이라고 떴다. 알고 보니 로컬에서 돌릴 때는 어떤 변수가 쓰레기값으로 초기화가 되었는데 채점기에서는 0으로 초기화가 돼서 틀린 거였다. 그래서 C에서 AC를 받았다.

30분 남은 시점에서 F (=학교를 쌓아올리는 포닉스, 오픈콘 E)를 봤는데 대충 아주 간단한 투포인터 문제로 보였다. 그 전에 그 문제 자체를 왜 못 봤는지 모르겠다. 다른 사람이 들고 있던 건가....? 이미 충분히 많은 팀들이 풀었는데, 사실 나도 멘탈이 나가서 슼보를 보고 남들이 푼 걸 풀어야겠다는 생각 자체도 못했던 것 같다. 내가 키보드를 잡은 상태에서 다 같이 F를 보기로 했는데, fixed가 멘탈이 나가 있을 동안 lyj랑 내가 병렬적으로 짰던 것 같은데 결국 둘 다 풀이를 못 냈다. 근데 사실 나도 건물 높이 1을 쌓는 것을 width번의 작업을 해야하는 걸로 생각하고 막 누적합을 짜네 마네 하고 있었는데 그 누구도 틀렸다고 지적을 하지 못한 것을 보면 다 같이 멘탈이 나갔던 것 같다. 내가 5분 정도를 남기고 구현 방향이 잘못되었음을 깨닫고 나중에 풀었던 정해에 가까운 풀이 방향을 떠올렸는데 (포인터 방향을 거꾸로 해서 바이토닉하게 만드는 것) 시간 내에 구현을 구체화할 수 없을 것 같아 결국 키보드를 내려놓았다.

결과

특별상을 받아서 총 30만원을 받는 데 성공했다! 시작 전에 긴장 풀기용 농담으로 X염색체의 수가 가장 많은 팀으로 기준을 정하면 상을 받을 수 있다고 주장했었는데 이건 아니었고 개삽질한 후에 AC를 받았던 C가 특정 제출 시간에 가장 근접했다고 한다.

순위 자체는 12/14등을 했다. (12/13등이었나?) 당연히 3등상은 받을 거라고 많은 사람들이 말했어서 이 정도의 성적을 받을 줄은 몰랐고 솔직히 너무 부끄러워서 숨고 싶었다. 그래서 특별상을 받았을 때도 사실 그냥 막 포닉스 굿즈. 시프트업 굿즈. 이런 거 줄 줄 알고 정말 앞에 나가고 싶지 않았는데 옆에서 누군가가 상금 인당 10만원이라고 알려줘서 개놀라고 '혹시 수상소감도 말해야 하나요?'라고 말했음 어이엑스

대회 이후

대회가 끝나자마자 티스토리에 올릴 후기의 일부를 작성했다. 아래는 그 내용의 일부이다.

사실 내가 읽은 모든 문제들은 실제로 내가 풀이에 아주 근접했고 충분히 풀었어야 하는 난이도였는데 하나도 못 풀었다는 생각에 많은 자괴감이 들었다. 

일단 대충 은퇴선언을 박고 양꼬치를 먹으러 갔다. 1,2등 팀이 우리 테이블에 앉았는데, B번이 어쩌네 L번이 정해가 뭐냬 하는 동안 나는 멍 때리면서 소주를 들이켰고 주량에 근접한 양을 마셨다. 이 때 후배들에게 빙홍차 소주 칵테일을 말아주고 '살면서 자기가 먹어본 소주 화합물 중 가장 소주 맛이 안 난다' 라는 극찬을 들었음 칵테일 동아리 3년 경력이 괜히 있는 게 아님

그러고 나서는 잔뜩 취해서 그 날 저녁에 있던 Div.2 코드포스를 친다는 후배들한테 나도 할까 같은 헛소리를 조금 했는데 내가 맛이 좀 많이 가 보였는지 괜히 레이팅 떨구지 말고 들어가시라는 소리를 들었다... (꼬장 부리는 선배라 미안해)

근데 방에 가기 싫어서 과방ㄱㄱ을했다 돔저지가 아직 닫혀 있지 않은 상태였기 때문에 제출이 가능했다. 일단 구현하다 말았던 F번(학교를 쌓아올리는 포닉스)을 짰다. 그 다음은 D번(부분수열의 개수)을 들여다봤는데, 슬슬 술이 깨면서 숙취에 대가리가 깨질 것 같았는데 난 이것도 못 할만큼 멍청하지 않아! 하고 눈이 감길 때마다 스스로의 대가리를 풀스윙으로 때렸고 과방에 모르는 사람도 있었는데 진짜 미친줄알았을거다 20분도 지나지 않아 정렬한 후 upper_bound로 2배 이하인 첫 번째 지점을 찾는 아이디어를 떠올려서 구현까지 마쳤다. 다음은 인터랙티브 H번도 봤는데, 이것도 차분하게 생각해보면 대소관계가 결정되면 수열이 결정된다는 걸 알 수 있었다. 사실 그 때 a, n+1-a가 둘 다 된다는 조건을 읽지 않았거나 이걸 어떻게 쓸지 몰랐던 것 같다.

이 때 정말 여러 가지 감정이 교차했는데, 아니 걍 만취에 가까운 상태에서 사실상 D, F, H를 혼자서 다 푼 건데 불과 몇 시간 전이었던 대회 때 맨정신으로 이걸 떠올리지 못했다는 게 어이가 없었고 동시에 '나는 대회를 망친 것 뿐이지 ps 자체를 개못하는 건 아니구나' 라는 안도감도 들었음 아직 접을 때는 아니구나... 그래 아무리 민트를 뽀록으로 찍었대도 이 정도는 아니야

여튼 그래서 접겠다는 주장을 철회하고 달콤한 잠에 들었다💤

팀원 회식

처음으로 돌아가 보자. PPC를 나간 것은 동아리 부원들과의 친목 목적이 가장 컸고 (여담이지만 PPC 작년 2등, 올해 1등을 한 chansolpark7이 팀이 없다고 같이 나가자는 제안을 받았었는데 이미 팀이 있어서 거절했다.) 실제로도 내가 친해지고 싶던 사람들과 편해진 것 같아서 기분이 좋았다. 그래서 특별상도 받았겠다 마지막으로 회식을 했다!

lyj: 백준 부활하면 연락ㄱㄱ 코테 준비할 때 필요함 

fixed: 역시 ps는 재미없다. 가서 선배님들 문제 푸는 거 구경하는 게 멋있었다.

하지만 재밌었죠 <3

마무리

역시 온사이트 대회는 정말 재밌는 것 같다. 코드포스라는 티어가 걸려 있고 시간 내에 문제를 풀어야 하는 환경을 경험해봤기 때문에, 대회도 마찬가지일 것이라고 생각했는데 팀 대회라 그런지, 제일 큰 대회여서 그런지, 부담감이 차원이 다르다...

마지막으로 우리 팀원 미소녀(fixed)와 운영진 미소녀(kyungdain)의 사진을 첨부하며 마무리한다. 이번에 정말 백준 섭종도 그렇고 여러모로 운영진 입장에서 진행하기 어려웠을텐데 대회가 성공적으로 끝나서 다행인 것 같고 정말 수고 많았다고 해 주고 싶다. 

강해져서 돌아오겠습니다.

(! 260518 13:11 오타 수정)

잠이 안 오는 새벽 세 시 반이다. 정수론 과제 소문제 하나에 1시간 반을 매달렸지만 결국 반쯤 이해한 채로 gpt의 풀이를 베껴서 내고, 인간관계에 대한 깊생도 들고, 해석학 시험은 얼마 남지 않았고, 최근 교내 ps대회도 말아먹고서 생각이 많아진 그런 날이라고 할까.

침대에서 뒹굴거리며 핸드폰을 들여다봤고, 2020년부터 사용했던 내 트위터 계정을 구경하며 나름의 추억팔이를 하다 '학교에서 수행평가로 나왔던 확통 문제인데 어떻게 푸는지 잘 모르겠다'는 내 질문글을 보게 되었다. 필자는 인과영 확통 내신에서 B-(석차로 따지면 9등급제 기준 8등급 정도)를 받았다. 중학교 2학년 때 잠시 중등 KMO를 준비할 때도 조합론 문제는 단 한 개도 맞추지 못했다. 조합론은 근사(not approximation yes cool)하고 재밌지만 묘하게 재능을 타며, 아쉽게도 나에게는 그 재능이 없다.

당시 설컴을 다니고 경곽 같은 데 다니던 멋진 트친 분들이 답장을 해 주신 걸 구경하는데 꽤나 흥미로웠다. 근데 읽다가 되게 많이 나오는 DP 문제 아님? 이라는 생각이 들었다. 그래서 풀어봤는데 이게 맞네?

이하 풀이:

더보기

일단 문제가 대칭적이기 때문에 첫 번째를 1로 고정하고 나중에 4를 곱할 것이다. i번째에 고른 수가 처음에 고정한 수와..

A[i]: 같은 경우 (ex. 1)

B[i]: 반대인 경우 (ex. -1)

C[i]: 상관없는 경우 (ex. i, -i) 

 

그러면 점화식을 세울 수 있는데 

A[i+1] = A[i]+C[i]

B[i+1] = B[i]+C[i]

C[i+1] = 2*A[i]+2*B[i]+C[i]

초깃값은 A[0]=1, B[0]=C[0]=0이다.

 

마지막도 반대이면 안 된다. 따라서 4*(A[n-1]+C[n-1])이 답이 된다.

 

여기에 식을 구하고 싶다면 A[i]+B[i]+C[i]=3^i (임의의 순간에 길이 i+1의 sequence를 만드는 방법은 직전 꺼를 제외한 나머지 3개이고 시작은 3^0=1이다)을 이용해서 식정리를 해주면 된다. 점화식을 풀면 길이 n에 대해 3^n+(-1)^n+2 라는 closed form을 얻을 수 있다. 악필이라 ㅈㅅ

당시 학교에서 배웠던 조금 더 고능한 조합론적 풀이도 첨부했다. 

더보기

고등학생 때의 내가 못 풀어서 결국 풀이를 외워버렸던 확통 문제를, 대학생이 되어 알고리즘 문제풀이를 시작하고 DP 문제로 바꿔서 풀어냈다는 점에서 스스로의 발전이 뿌듯하게 느껴졌다. ps가 절대적인 발상력을 높여주는 건 아니지만 가능한 발상의 폭을 넓혀주긴 하는 것 같다. 대학교 와서 뭘 했지? 라는 생각을 아주 많이 했지만, 사실은 나도 모르게 조금씩 성장했을지도 모른다. (ㅈㅅ 제가 씹덕이라 성장, 결실 같은 키워드에 환장함)

+ LLM에게 풀이의 유효성을 검증받았더니 4-state graph에서 길이 n의 walk를 계산하는 문제로 환원할 수 있다고 해서 신기했다. 뭔진 잘 모르겠지만 만약 알고리즘에 대한 내 관심이 계속된다면 그래프의 성질도 공부해보면 재밌을 것 같다. (뭐든 쉽게 질리는 성격 탓에 그럴진 모르겠긴 함)

+ 백준에 동일한 문제가 있을까? 하고 검색해보려고 했는데 아 백준이 없어졌구나... 라는 걸 깨달았다. 주변인들에게 물어봤더니 실버~골드하위 DP이고 식까지 구하는 건 골드 상위~플레 하위라는데 그럼 난 실버랑 골드를 풀고 신나서 블로그 글을 쓴 거구나(!) 좀 부끄러워졌을지도?

+ mathtw1030님이 알려주셨다! 이게 있네?

오늘은 제 인생 첫 PS 대회입니다. 기대 반 걱정 반 (기대 10% 걱정 90%)로 포항행 기차에 몸을 싣었습니다. 

이하 잡설이 많습니다. 또한 POSTECH 참가자들끼리 뒷풀이를 진행하며 음주 상태로 작성되고 있으며 퇴고를 거치지 않았기 때문에 문장 coherence가 부족할 수 있는데 틀린 내용이 있으면 알려주세요.

시작도 전부터 2가지 정도의 억까를 겪어버립니다!

1. 서울-포항 기차 없음 이슈로 8시 기차를 타야 해서 7시 반에 일어났습니다. 보통 3시 정도에 규칙적으로 자는 사람으로서, 7시 반 기상으로 인해 다소 피폐해져서 커피 두 잔과 박카스 한 잔을 도핑합니다.

2. 충전기를 본가에 놓고 왔습니다. UDPC를 치다 말고 컴퓨터가 꺼지면 어떡하지 같은 근들갑에 잠시 정신이 사로잡혔지만 에이 설마 3시간은 버티겠지 같은 생각으로 마음을 가다잡았습니다.

이건Div3코포다이건Div3코포다이건Div3코포다이건Div3코포다이건Div3코포다괜찮다긴장하지말자제발긴장ㄴㄴ 문제를 풀어 봅시다.

A (대회 장소 정하기)

(0:45 AC)

UDPC는 난이도순이라는 말을 분명하게 들었습니다. 나름 0917ba가 홍보할 때도 뉴비 친화적인 대회라는 이야기를 했었습니다. 그러니 아마 A번은 대충 브론즈 사칙연산이겠죠? 모든 재앙의 시작

음 뭔가 생각보단 케이스가 많을 지도 모르겠습니다. 대충 선을 일직선으로 편 후에 구간에 따라 나누면 될 것 같고, 위치에 따라 나눠서 하면 될 듯 합니다. 그러니까 min(거리, N-거리) 이런 쌍을 잔뜩 만들어서 케이스워크를 하면 될 것 같습니다. 문제는 그것을 어떻게 하느냐입니다. 이것은 능지를 요구하는 정신 나간 케웍 문제이며 저는 능지가 없습니다. 막 모든 케이스를 다 나눠서 하면 될 것 같은데 실수하면 끝장 아님? 내가 첫 ps 대회에서 0솔을 하면 어떡하지? 여기서부터 멘탈이 갈리기 시작합니다. 

그나마 다행히도 멘탈이 덜 갈리게 된 점은, 15분이 경과했는데 아직까지 A를 푼 사람이 한 명(인가 두 명인가)밖에 없었습니다. 이 문제는 아무래도 A번 난이도가 아닌 것 같습니다. B로 넘어가 봅시다.

B (포닉스와 달구 2)

(+1 1:25 AC)

그래서 B를 읽기 시작합니다. 흐으음... B도 무슨 게임이론 construction처럼 생긴 문제입니다. 진짜 죽일까(not 출제진 yes 문제)? 그래도 A 같은 케이스워크를 하다가 이미 예제가 안 나오는 상태였던지라 이거라도 풀어야겠다는 생각이 들었습니다. 이걸 못 풀면 진짜 0솔을 할지도 모릅니다.

직관적으로 0...0 과 같이 대칭인 0의 쌍이 있으면 선공이 비대칭을 만들 수 있고, 1...0과 같이 비대칭이고 한 쪽을 채울 수 있는 게 있다면 이건 후공 입장에서 언젠가 해결해야 하는 숙제입니다. 그러나 원래 일퀘라는 건 하루에 하나만 할 수 있는 것이기에, 후공도 마찬가지로 이 숙제를 하나만 할 수 있습니다.

따라서 선공이 1...0 쌍을 항상 2개 이상으로 유지하면 무조건 이기..나? 이렇게 생각하고 코드를 짜봤는데 엥? 예제가 안 돌아요. 당연히 이렇게 간단할 리가 없습니다. 대충 이런 관찰을 몇 개 더 하면 풀리겠죠?

대칭이라는 건 홀짝성에 따라 가운데가 있을 수 있습니다. 가운데가 아직 채워져 있지 않은 경우는 뭔가 여분의 수?가 하나 생깁니다.

선공이 여기에다가 두면, 아무 일도 일어나지 않지만 후공이 복구할 0...0 쌍을 안 만드는? 효과가 있습니다. 근데 후공의 턴이 오지 않으면 승리한다고 합니다. 그 말은 1...0 쌍 <2 인 경우를 분리해서 생각해줘야한다는 건데, 1 이하인 경우 무조건 후공이 이긴다고 대충 생각하고 제출을 눌렀는데 WA.  

안 되곘습니다. 저는 이런 고능한 게임이론 문제를 풀기에는 너무 저능합니다.

차라리 A는 가능한 모든 경우를 해 보면 될 것도 같으니 A로 다시 돌아가 봅시다. {시계, 반시계}, {ans, N-ans}를 나눠서 모든 경우의 min()해버리면 되지 않을까 같은 생각으로 케웍을 했고 다행히 예제가 돌아서(?) AC!

(주석: A번의 경우 나중에 뒷풀이에서 Equinox 군의 이야기를 들어보니까, n<=100이기 때문에 그냥 스트레스를 짜도 O(n^4)인데 간당간당하게 1초 안에 돈다고 합니다. 역시 ps 짬바가 있으면 이러한 발상도 가능한 듯)

휴! 이젠 B를 좀 풀어야겠습니다.

하루에 숙제를 두 개 이상 못한다는 이론을 일단 붙잡아보기로 했습니다. 이걸 좀 더 세분화하면 되지 않을까요?

근데 사실 두 개 이상이 아니라 세 개 이상일지도 모릅니다. 왜냐하면 [가운데를 채우기]라는 스트릭프리즈가 있기 때문이죠.

• 1...0 쌍이 3개 이상이면 절대 안 됩니다.
• 1...0 쌍이 없는 경우는 0...0 쌍이 있고 가운데가 비어 있으면 됩니다.
• 1...0 쌍이 한 개인 경우, 0...0 쌍이 없으면 후공 차례가 안 와서 선공이 이기게 됩니다. 0...0 쌍이 있으면 후공이 채우면 됩니다.
• 1..0 쌍이 두 개인 경우, 0...0 쌍이 없으면 후공이 대칭으로 항상 만들 수 있습니다. 대신 가운데가 비어 있으면 가운데를 채워서 턴을 벌 수가 있으므로 이 경우는 제외합니다.

직접 예제를 몇 개 만들어봤을 때 다 되는 것 같길래 믿음의 도약으로 제출을 눌렀고 AC를 받았습니다. 이 케이스워크를 하기에 너무 저능해서 좀 오래 걸렸습니다.

어케했지? 케웍이나 construction은 풀 때마다 내가 빼먹은 끔찍한 케이스가 있지 않을까 같은 불안감을 떨칠 수가 없는 것 같는데 이거 어떻게 해결하나요

C (U-DeeP-See)

(1:35 AC)

제 닉네임이 드디어 슼보에 보이기 시작합니다. 이 때부터 좆됐다는 생각이 좀 사라지면서 긴장이 풀리기 시작합니다.

C번도 construction입니다. 저는 ad-hoc, construction, greedy에 약하고 DP, graph에 강한데 (물론 골드 중하위의 문제 따위를 풀며 제가 이딴 소리를 하는 것도 좀 웃기긴 합니다.) 아직까지는 제가 못하는 것만 한가득입니다.

(주석: PS를 처음 시작한(?) 시점에서 반 년 정도 지났는데, 골드 이하의 문제를 보면 대략적인 태그가 예측 가능합니다. 고슈분들의 블로그를 보면 '이건 애드혹이니까 qwer에게 던지고 이건 자료구조 비빔밥 같으니까 asdf에게 던졌습니다' 같은 말들이 있어서 저도 태그를 안 상태에서 팀원에게 문제를 던지고 싶다는 생각을 자주 하는데, 문제는 저에겐 던질 팀원이 없으며 제가 풀 능력도 없으니 큰 의미는 없습니다.) 

2d grid sum (있는 말인가?)는 근본적으로 convolution 이라는 생각이 들었습니다. 참고로 이 토픽은 2023 UDPC 셋을 돌 때도 나온 적 있는 토픽인데, 당시 ijkxyz의 늪에 빠져서 구현에 실패하고 나중에 업솔빙을 했었습니다.

다행히 UDPC는 인터넷 검색이 가능합니다! 바로 convolution 공식이라고 구글에 검색했는데 합성곱 컨볼루션이 먼저 뜹니다. 아니 CNN 컨볼루션 말하는 건데; 그리고 Google AI Search가 그 밑에 뜹니다. 이러다가는 생성형 AI 사용으로 실격을 당해버리면 슬플 것 같습니다.

아니 생각해보니까 output kernel 공식은 이게 뭐 검색할 정도의 것도 아닌데 왜 검색했지?

빠르게 창을 닫았습니다. 

홀수일 때는

     -1

-1 +4 -1

     -1

이런 격자를 만들면 되겠지? 그렇다면 짝수일 때는 일반화가 가능할까요?

아니 근데 그냥 각 n_output마다

-1 -1 -1 -1

1 1 1 1 

이런 걸 하면 합은 보존되는 것 아님? 제출을 하고 빠르게 AC를 받습니다. 뭐지 나 construction 잘하나?

D (카드 섞기 게임)

(+1 1:59 AC)

a[i]를 s[a[i]]로 매핑하는 operation을 k번 했을 때 사전순으로 최소가 되는 문자열을 짜면 됩니다. 아니 난이도 순이라며 이게 A보다 쉬운 것 같은 건 기분 탓임? 제가 수학을 잘 못해서 이게 수학적으로 용어가 맞는진 모르겠는데, f^m(x)=x가 되는 주기 m이 있을 거고 k%m을 해서 원래 문자열의 합성을 O(n^2) 안에 구할 수 있습니다. a[i]를 s[a[i]]로 매핑하는 형태의 문제는 코드포스 같은 곳에서 많이 봤기에 거의 보자마자 짤 수 있었습니다.

그러나 예제조차 돌지 않는 맞왜틀의 저주에 빠져버리고 맙니다. 하아.... 아무리 봐도 제 코드에 틀린 게 없습니다.

혹시 s[a[i]]를 ans[a[i]]로 반대로 매핑했나?? 혹시 array 초기화를 잘못했나?하고 모든 프로토콜을 돌려봅니다. 이게 뭐 풀이가 복잡한 문제도 아니고 틀릴 리가 없습니다. 2차 멘탈 붕괴가 옵니다.

이 시점에서 스코어보드가 프리즈 됩니다. 이 시점에선 다행히 6등이었는데 10등까지 수상이니까 수상권 밖으로 밀려날 것 같다는 걱정이 들었습니다.

다음으로 풀 문제를 찾아야 합니다. E (풍선줄 자르기), G (송신탑 설치) 정도가 후보입니다. G번은 예전에 코포에서 봤던 문제인 것 같습니다. 그래서 규정에 따르면 이미 짠 코드를 사용할 수 있다고 했기 때문에 코포 제출 내역을 다 뒤져봤는데 그 문제가 보이지 않습니다. 뭐지 꿈에서 풀었나?

아니 다시 생각해보니까 D에서 처음에 매핑을 시작하기 전에 시작 string을 정렬을 했어야 되는데 안 했네요. D를 못 풀었다는 생각에 너무 답답했었는데 이걸 찾아냈다는 생각에 막 손이 떨렸고 수정 제출을 눌렀는데 너무 흥분한 나머지

1. E에다가 제출을 (두 번이나) 누르고,

2. 이걸 깨닫고 다시 D에다가 제출을 했는데 cout<<ans를 쓰지 않고 제출을 하는

블런더를 저질러서 E와 D에 WA를 하나씩 쌓는 레전드 사건이 일어납니다... 진짜 얼탱

E (풍선줄 자르기)

(+1 2:57 AC)

이제 시간이 약 20분 정도 남았습니다.

E를 자세히 읽어보니 그냥 흔한 경로 찾기 문제입니다. 남겨놓은 선의 길이의 최댓값을 구하는 문제로 생각하고 MST 문제라고 착각을 해 버리고 맙니다.... 그래서 일단 다급하게 제 union find 템플릿을 찾습니다. UDPC의 경우 어떤 팀노트도 사용 가능하고, 인터넷 검색도 자유롭지만, 코드를 복사를 하면 안 된다는 규정이 존재합니다. 그래서 이 순간부터 저는 인간 복사기가 되어 제 5nn타의 초스피드 영타로 템플릿을 치기 시작합니다.

근데 다시 읽어보니까 풍선의 높이들의 합의 최소를 구하는 거잖아? 아니 시1ㅂ 다익스트라잖아 ㅋㅋㅋ 다익스트라 템플릿을 찾습니다. 이 시점에서 시간이 10분 정도 남았습니다. 이제부턴 내가 과연 10분 안에 다익스트라 템플릿을 짤 수 있을까?에 대한 문제입니다. 정말 다행히도 딱히 변형할 게 없어서 그냥 그대로 쳤고

버저비터로 AC를 받을 수 있었습니다! 캬

손이 덜덜 떨리고 토할 것 같아서 끝나자마자 화장실로 달려갔는데 이렇게 손 떨리는 경험은 대학교 입시 이후로 처음이었습니다.

카페인 때문이었을까요 대회 때문이었을까요? 몰?루

결과: 5솔로 6등(4등상)을 받았습니다!

여담으로 슼보 깔 때 진행자가 3x3x173은 얼마일까요? 계산을 해 보겠습니다 하고 계산기를 냅다 켜더니 1557입니다. 이래서 좀 웃겼음

후기

팀노트도 되고 인터넷 검색도 되기 때문에 사실상 코드포스 Div.3를 치는 기분이었는데 실전 대회라는 압박감이 엄청납니다. 사실 저는 평소에 B 같은 복잡한 게임이론 construction을 짧은 시간 안에 깔끔하게 잘 떠올리지 못하는데, 이걸 해냈다는 게 역대급 고점을 띄워서 기분이 좋습니다.

그리고 뭔가 난이도 순이라고 해도 내가 느끼는 난이도와 진짜 난이도는 다를 수도 있겠다고 생각했습니다. 저에게는 A가 너무 어려웠어서 이 때 멘탈이 나갈 뻔했는데, N 범위 보고 브루트포스 같이 말렸을 때 뚫을 만한 좋은 방법들도 생각해두면 좋을 듯?

다음 고점은 PPC 때 띄우고 싶습니다. 파이팅!

end

How CPUs Communicate with I/O Devices

옛날에는 높은 bandwidth (GB/sec)의 Memory Bus와 I/O Bus (100MB/s)를 분리

요즘은 I/O, memory 둘 다 high-bandwidth interconnect 사용

I/O Mechanisms

1. I/O port registers

• I/O 목적으로 만들어진 register를 사용.
• microcontroller에서 많이 사용
• 장점: simple, low-latency, specialized
• 단점: I/O signal 개수가 한정적

2. Memory-Mapped I/O (mmap I/O)

• “Load/Store instruction”으로 I/O
• unused memory register → “mapped” to registers of external devices
• A write (SW addr, value) to a mmap address (like 0xffff0000) means:
• A read (LW reg, addr) from a mmap address means:

• idempotency (멱등성) 문제.
• mmap I/O address는 절대로 cache해서는 안 된다.
• 단점: word 단위로 읽게 되면 느리다.

3. Direct Memory Access (DMA)

• 말 그대로 I/O device들이 메모리에 직접 access하는 것
• mmap write를 통해 I/O device에게 직접 명령을 내리고, write가 끝나면 interrupt
• DMA engine command: “어떤 source block에서 destination block으로 데이터를 복사해라”
• 문제점: Cache coherence 문제 발생

DMA, mmap I/O 비교

DMA: virtual memory problem

DMA에서 VA 사용

• command만으로 쉽게 큰 용량도 복사할 수 있다.
• 그러나 VA를 PA로 번역하는 과정이 복잡하다

DMA에서 PA 사용

• translation은 필요 없다
• DMA command를 바로 쓸 수 없다.
• buffer가 PA에서 contiguous(연결되어 있고), Page boundary를 넘어가지 않는지 확인해야 한다.

Software solution: pinned page로 고정

• DMA에서 사용할 address에 대해서는 미리 특수한 page를 할당한다.
• 따라서 VA page이긴 하지만 이에 대응하는 PA page가 항상 고정되어 있다는 특징이 있다. (Pinned contiguous pages → translation becomes trivial)
• 주소 변환 없이 DMA 장치가 직접 접근이 가능해진다.

Hardware solution: (이해못해도 생략)

• Smart DMA+linked list: OS가 연속되지 않은 물리 메모리 블록들을 linked list 형태로 만들어서 page-level transfers들을 따라서 gather (read) / scatter (write) 한다.
• Virtually-addressed I/O bus: VA를 I/O TLB를 이용해 PA로 미리 바꿔둔다.

Device Interaction Models (when to serve I/O devices?)

Polling I/O: CPU가 I/O 상태를 직접 계속 확인

• READY 레지스터: 새로운 값이 있으면 true
• DATA 레지스터: 새로운 값을 반환, ready를 리셋
• I/O가 infrequent한 경우 비효율적

Interrupt-Driven I/O: CPU가 I/O 상태를 직접 계속 확인

• 위의 _checkkbd를 interrupt handler가 부르는 것
• infrequent event, long-latency (오래 걸리는)에 좋음

그래서 어떤 걸 쓰냐

• Latency (지연 시간) = {고정 오버헤드} + {데이터 크기 / 전송 속도}
• Effective I/O Bandwidth = 전송 크기 / 전체 지연 시간

를 고려해서 결정

• Interrupt I/O: 드물지만 즉시 반응해야 하는 이벤트에 적합 (ex. 키보드 입력)
• Polling I/O: 자주 반복되는 고속 데이터 처리에는 적합할 수 있음 (ex. 네트워크 패킷 처리)

Bus Architecture and Protocols

Bus = 여러 장치들이 공유하는 데이터 경로 (broadcast medium)

• 비용↓, 간단함↑
• 하지만 동시 접근 불가 → bandwidth를 순차적으로 쉐어한다.

Device types

• Master: transaction을 보내는 장치 (예: CPU)
• Slave: transaction에 응답하는 장치 (예: DRAM, I/O)

** 하나의 device가 master, slave 둘다일수도 있다.

• Arbiter: 버스를 사용할 수 있는 순서를 정함

Bus transaction 순서

CLK 에 따라 모든 디바이스가 싱크되어 있고

1. Master → 버스의 ownership을 요청 (REQ)
2. Arbiter → 승인 (GNT)
3. Master → 주소와 명령 전송
4. Slave → 해당 주소가 자기 것인지 확인 후 claim
5. Read면 Slave가 데이터를 전송, Write면 Master가 데이터 전송
6. transaction 종료

이 때 “Broadcast” signal은 모든 device가 공유한다.

• R/W: 읽기인지 쓰기인지 구분
• AD (address/data) bus: 주소와 데이터를 공유 버스로 전송

separate address bus and data bus? → 성능 ↑ 하지만 비용과 복잡도 ↑

Asynchronous Bus Protocols

• clk 없이 각 단계가 준비될 때마다 **핸드셰이킹(handshake)**으로 진행
• 장치마다 access latencies 달라도 무방
• ex. REQ/GNT is an asynchronous handshake

핸드셰이킹 방식: MRDY & SRDY

• AD value가 유효할 때만 MRDY, SRDY를 1로 만든다.
• Bus cycle은 MRDY && SRDY == 1일 때만 유효하며, 데이터 전송이 유효해지는 것.

장점:

• transaction당 오버헤드(REQ/GNT 등)를 여러 데이터에 분산시킴
• Bandwidth 활용도 향상, 캐시 라인처럼 fixed size block 전송에 적합

Bus Performance

1. Latency

Arbitration Latency (=중재, 여기서는 버스 권한 요청을 의미)

• Bus contention (bus 사용 경쟁),
• Arbiter의 arbitration policy에 따라 달라짐

Transaction latency

• slave reaction time

2. Bandwidth

Peak bandwidth = N x f (N-byte AD bus operating at frequency f)

• Request/Grant 단계
• Address/Claim 단계
• Termination 단계

data bandwidth와 상관없는 overhead cycle이 많아질수록 bandwidth가 떨어짐

오버헤드를 burst로 전송해서 효율 향상

Fixed-sized burst on synchronous, Variable-sized burst on asynchronous protocols

Widely Used Buses

참고: 요즘 “버스”는 대부분 Point-to-Point 인터커넥트

• Examples: PCIe, USB, Firewire, Thunderbolt (slide 28)
• Parallel buses: SCSI, ATA (slide 29)
• Serial buses: SATA, SAS (slide 30)

Multithreading

• 하나의 core 안에서 여러 process를 parallel하게 (병렬적으로) 돌리는 것
• Process = 하나의 virtual address space를 의미
• “Thread” = shared VA space
• 하나의 thread에서 시작해서, program state (memory/register 등) 를 복사해서 각각이 독립적인 PC와 stack을 가지도록 한다.

pthread 예시

• pthread_create() starts a new thread.
• pthread_join() waits for a thread to complete.

Data race

서로 다른 thread가 shared memory를 동시에 바꾸면 안된다

critical section: 이 구간은 한 번에 하나의 thread만 실행되어야 한다.

ex. CS61C 자료를 참고하도록 하자

Use a lock

critical section 전에 Acquire(L), 후에 release(L)

L은 lock variable의 memory address를 의미한다. 0=unlocked 1=locked

pthread_mutex_lock(&my_mutex) 를 사용하면 됨

Atomic Read-Modify-Write (RMW)

Acquire(L)을 구현하기 위해서 atomic instruction이 필요하다. hardware 차원에서의 locking을 하는 것.

Test&Set (addr, r)

M[L] = 0이면 lock이 free이다

M[L] = 1이면, 다른 thread가 이미 acquire했다.

Test&Set (L, r):
	r = M[L]      // test를 위해 lock의 register에 있는 value값을 r에 넣어줌
	M[L] = 1;     // 1로 set을 시킴

Acquire(L)
do {
    Test&Set(L, r);      // Try to grab lock
} while (r != 0);        // Retry if lock was already taken

Release(L)
M[L] ← 0                     // Release lock

Compare&Swap (addr, r_exp, r_swap)

r_comp라는 expected value와 M[addr]을 비교한다.

만약 같으면 Swap: M[addr] 자리에다가 r_swap 넣어주는 것

이걸 성공하면 0, 실패하면 1을 반환한다

Acquire loop에서는, r_swap=0인지 확인한

Compare&Swap (addr, r_exp, r_swap):
	if (r_exp == M[addr]):
		Swap(addr, r_swap) // M(L)의 값을 r_swa로 업데이트

Acquire(L)
do {
    r_exp ← 0; r_swap ← 1;
    Compare&Swap (addr, r_exp, r_swap);
} while (r_swap != 0);

Release(L)
M[L] ← 0

lr.w, sc.w를 이용해 non-atomic instruction들을 합치면

🔹 lr.w rd, (rs1) — Load-Reserved

• rs1 에 있는 address에 있는 값을 rd register destination에 저장한다는 점에선 일반적 read랑 똑같음
• 다만 lr.w 는 “나 여기다가 곧 write할래”라고 예약을 해놓는 것.

🔹 sc.w rd, rs2, (rs1) — Store-Conditional

• addressrs1 에다가 rs2 에 있는 값을 저장한다.
• lr.w 이후로 다른 store 요청이 없었으면 성공 → rd = 0 을 입력
• 이외의 모든 경우 rd ≠ 0

Coherence vs consistency

• Coherence: local ordering— 하나의 memory location에 read/write할 때.
• Consistency: global ordering— 서로 다른 Memory location의 연산 순서가 Memory model을 consistent하게 따른다.

Sequential consistency

예를 들어 이건 실행 순서에 따라 (0,0)이 될수도, (0,1)이 될수도, (1,0)이 될수도 있다.

SC의 정의

프로세서들이 memory operation들을 global memory에 요청해서 처리할 때, 처리 순서는 랜덤할 수 있으나 program order는 유지되어야 한다. 이렇게 모든 연산을 하나의 global ordering으로 나열할 수 있으면 그 시스템은 Sequential Consistency를 따른다고 한다.

SC의 조건

1. 어떤 thread 안에 있는 메모리 연산은 항상 순서대로 실행해야 함
2. 서로 다른 프로세서에 있는 메모리 연산은 임의로 섞일 수 있다. (interleaved arbitrarily)
3. 각 실행에 대해서 모든 thread는 global ordering, 즉 같은 순서로 메모리를 연산을 인식해야 한다.

예를 들어

T1: store(X, 1); Y’ = load(Y);
T2: store(Y, 1); X’ = load(X);

Y’ = 1, X’ = 0 는 SC 모델에서 불가능하다. (그냥 머릿속에서 직접 실행 해 보면 알 수 있음)

Mutual exclusion:

서로 다른 thread가 critical section에 동시에 진입하지 않도록 하는 것

SC의 단점

• 지나치게 restrictive하다. (critical section이 아닌데도 out-of-order access를 다 막음)
• Out-of-order CPU와 공존하기 힘들다.

Store buffer

• Store 명령 → store buffer에 임시로 저장
• Load 명령에서 같은 주소를 읽음 → 메모리 대신 store buffer 검색해서 값을 읽어옴
• Memory에 실제로 store하는 건 나중에 처리.
• OoO execution에서 많이 활용

문제 발생: P1, P2에서 write를 했는데 buffer에 들어있어서 업뎃이 안되면 critical region으로 들어가버릴 수 있음 (사진참고)

해결 방법?

1. Memory consistency를 weak/relaxed로 바꾼다. (일부 연산 순서는 바꿔도 되게 한다)
2. Speculatively ignore ordering rules (순서 몇 개는 추측해서 무시해버린다)

Address translation: EA (effective address) → PA (physical address)

Virtual memory가 있으면 어떤 점이 좋은가?

• Naming and Protection
• Demand Paging

Base and Bound Registers

process가 메모리에 접근할 때는 base(시작), bound(끝)를 기준으로 한다

user process는 EA (effective address) 기준으로, 0부터 메모리 사이즈까지 배정시킨다.

Address translation

• PA: physical address, EA: effective address
• PA = EA+base, check if PA<bound
• Base, bound는 user process (x) privileged mode(o)에서 수정해야 함

그러나 Base & Bound의 단점들이 존재하는데….

Fragmentation

• External fragmentation: free memory가 서로 안 붙어있을 때 (non-contiguous)
• Internal fragmentation:

Sharing

서로 다른 memory space가 일부 memory만 쉐어하는 게 어려움

그래서 나온 것이 segmented ~

Segmented address translation

• 각 process마다 Code segment, Data segment, Stack segment… 이런 식으로 별도의 segment 이 존재한다.
• Segment table에 base&bound pair가 여러 개 있으며, 메모리를 일부분씩 사용한다.
• EA (effective address)의 구성은 다음과 같다

Translation 메커니즘

• Segment translation table이 존재해서, physical address로 매핑해준다.
• translation table은 privileged structure여야 한다

• how to change the mapping when swapping processes?:

Protection bit

• Segment table에 base, bound 이외에도 extra bit들을 추가하기도 함. (Readable? Writeable? Executable? Cachable?)

Paged Address space

• EA space (virtual memory)를 page라는 block으로 나눈다. 쉽게 말해, page: virtual memory block (fixed size)인 것.
• 이 page가 (physical memory에 있는) frame으로 매핑된다. page frame: page에 해당하는 physical memory
• Page table이 EPN을 PPN으로 translate한다

Demand paging

Virtual memory를 처리하는 방법 중 하나로, 말 그대로 page를 필요할 때만 DRAM에서 직접 불러오고 필요없는 페이지들은 하드디스크에 저장

• main memory+disk를 자동으로 manage되는 hierarchical memory system으로 사용한다.
• disk (swap space)를 memory page에 대한 백업 용도로 사용하고 program이 DRAM에 없는 페이지에 접근할 경우 page fault로 OS가 DRAM에서 page를 불러온다.
• miss penalty가 큰 대신에 (dram에서 직접 불러와야 하기 때문에) miss rate가 적음 (page 자체가 크기 때문에)

Page table

• VPN (virtual page number) → PPN (physical page number)로 매핑해주는 일종의 디렉토리
• PTE(page table entry)들의 array

page table은 present bit=1 이면 page frame으로 매핑 되어 있고 (virtual memory address에 해당하는 physical memory가 있다는 뜻) present bit=0 이면 disk로 매핑되어 있다.

Page hit (Present bit = 1)

• PPN + offset → physical address

Page fault

• VM에 있는 word에 접근했는데, 그게 physical memory에 없을 때
• Page fault는 OS의 page fault handler에서 해결함 (cache miss와는 다르게)
• DRAM에서 비어 있는 page frame이 없으면 eviction이 일어나게 된다.

1. Page replacement: evict할 virtual page (예시에서는 vp 4)가 변경되었으면 (dirty이면) disk에 다시 write를 하고, 원래 physical address가 있던 자리에 disk address를 써준다.
2. Load requested page: 아까 비웠던 page frame에 새로운 virtual address를 불러와서, PPN

이 과정 자체를 demand paging이라고 함.

Page size (2021 기출)

• Page size가 크면,

Paged memory

Physical memory (DRAM)을 page 단위로 나눈다.

disk access: page 전체를 memory로 load한다.

• memory translation: VPN (virtual page number)를 physical page number (PPN)로 바꿔주는 것
• 이는 page table을 기준으로 한다. PTE (page table entry)에 써있는 걸 보고 virtual address를 physical address로 바꿔준다.
• Page table은 memory에 있다.
• page가 memory에 있다 → corresponding physical page number가 있다.

• page가 memory에 없다 → page fault가 되며, OS가 disk에서 page를 읽어오도록 한다.

연습문제?

“machine”→ virtual address에 해당

RAM → main memory의 용량이므로 physical address에 해당

page offset = 16 * 2^10 = 2^14 → 14 bits

VPN: virtual address에 해당. 32 - 14 = 18 bits

DRAM = 2^33 bytes. 33 - 14 → 19 bits

Page table에는 VPN 하나당 1개의 entry가 존재한다. (그러나 VPN의 모든 숫자가 PPN과 매칭되진 않을 수도 있음) each entry is 4B → 2^18 * 4 = 2^22 = 4MB

또한, 각 process당 1개의 page table이 존재한다.

연습문제

4KB page = 2^12 bytes → page offset: 12 bits

VPN: 32-12 = 20 bits

16GB DRAM = 2^34 bytes → 34 bits of physical address

PPN: 34-12 = 22 bits

Virtual page size = physical page size = 4KB

# of page table entries = # of virtual page numbers

Virtual memory system의 장점?

• 각자마다 private address space가 있기 때문에, 프로세스 간에 memory를 isolate할 수 있다.
• Demand paging을 통해서, DRAM의 용량보다 큰 program도 돌릴 수 있게 된다.

Page table의 status bits

• Access type
• write protection bit: 위에 말한 protection의 차원에서 write를 해야 하는 경우에 대해서만 write하도록 한다.

page table 사이즈를 줄이는 방법

그 동안은 virtual address마다 전부 PTE가 있었음. 그러면 page table이 너무 많은 공간을 차지하게 된다는 문제점이 있음!

Hierarchical (multi-level) page table:

• "tree structure” = 각 레벨의 PTE가 하위 레벨의 PTE entry를 가리키는 포인터 같은 역할을 하는 것.
• sparse address space에 대해서 효율적이다. (L1 entry를 그냥 null로 보내버리면 되기 때문에)
• Locality가 클수록 fragmentation이 덜 되어서 공간 활용이 더 효율적이다. (쉽게 말해 L1의 포인터가 모두 L2에 있는 걸 가리키고 있어야 좋다)

Hashed (inverted) page table

(Process ID, VPN) → PPN으로 매핑

hashing을 이용해서 VPN ⊕ PID를 정해진 사이즈로 hashing 한다.

page miss의 경우 hash collision chain을 찾는 거 빼면 똑같다

⇒ address space가 매우 크고 virtual memory가 sparse할 때 활용하면 좋다

TLB (Translation Lookaside Buffer)

= 쉽게 말하면, cache of most recently used translations

given a VPN → return PTE

TLB entry:

주어진 VPN에 대해서 PTE를 return한다

tag: PID (process ID) + part of virtual address

Access process

ex. 0x00403FFC 라는 주소를 access 하고 싶다고 하자.

Page size: 4KB

VPN: 0x00403 / Page offset: 0xFFC

1. TLB에서 0x00403을 찾아보자 → 있으면 거기에 해당하는 PPN + page offset 해서 그대로 불러오면 된다
2. 엥 없네 → page table walk!

TLB를 HW or SW, 어디서 관리하는가?

• Hardware: RISC-V, x86, ARM, etc.
• Software: MIPS, etc.

VM과 cache의 관계

• Cache는 physical address를 필요로 하는데 CPU는 virtual address로 시작한다.
• VIPT cache (Virtually-indexed, physically-tagged) cache를 사용한다.\

Virtual cache의 문제점?

1. Homonyms (동음이의어): 서로 다른 2개의 process에 같은 virtual address가 있는 경우, virtual address가 같은데 PA가 여러 번 caching 될 수 있다. → TLB/cache를 PID로 tag해서 중복 방지
2. Synonyms: 서로 다른 virtual address가 같은 physical address를 가리키는 현상을 의미한다.

VIPT (Virtually Indexed, Physically Tagged)

virtually indexed: Virtual Address의 VPN을 이용해 TLB에서 PPN으로 바꾸는 동안

physically tagged: Cache에서는 page offset을 이용해서 cache 안에서 indexing을 한다.

이후, physical tag를 비교해서, match이면 cache hit이 된다.

• VIPT를 쓸 수 있는 조건? Cache size / Associativity = set size ≤ Page size
• Cache set을 인덱싱하는 비트가 page offset에서만 와야 한다.

ex)

• Page size = 4 KB → 2^12 B → 12 bits of offset
• Cache size = 32 KB
• Associativity = 4-way
• 8KB= 2^13B set size
• set size > page size 이기 때문에 synonym 발생. (aliasing)

Case study: virtual memory in x86

이론적으로는 segment를 이용한 2-level address translation

48-bit address

segmentation을 요즘은 거의 안 쓰고, EA = VA(거의같음) Paging으로 대부분의 isolation과 protection을 해결함.

On context switch: memory management unit한테 page table에 대해 다른 pointer를 사용하도록 한다.

The Law of Storage

1. Bigger capacity → Higher latency (걸리는 시간: SRAM < DRAM < SSD)
2. Faster 비싸진다 (SRAM > DRAM > SSD)

Basic Principles

Locality

• 프로그램에서 어떤 address에 있는 data와 instruction을 사용했으면 조만간 비슷한 곳에서 사용할 가능성이 높다
• Temporal Locality: 최근에 reference했으면 또 사용할 가능성이높다. (ex. loop)
• Spatial Locality: 근처 주소에 있는 것을 또 reference할 가능성이 높다

Cost amortization

DRAM에 한 번 access해서 데이터를 가져온 다음에 cache에 저장을 하면 된다.

One-time-overhead = DRAM access 시간

Per-unit-cost = cache access 시간

Cache

Access time이 상대적으로 짧은 컴퓨터 메모리로, 최근에 사용했거나 자주 사용한 instruction/data 등을 저장해놓는 것이다.

Memory Hierarchy

자동으로 관리할 수도 있고, 수동으로 관리할 수도 있다. GPU, special-purpose processor 등에서는 수동으로 관리하기도 하지만 너무 번거로워서 잘 하지 않음.

Register file → L1 cache → L2 cache → L3 cache → Main memory(DRAM) → Hard disk/SSD

• Register spilling: Register file은 CPU 안에 있어서 매우 빠르다. 만약 필요한 variable이 register보다 많은 경우, 컴파일러가 일부분을 L1 cache로 “spill”한다. 이는 하드웨어가 아닌 compiled code에 의해서 관리된다.
• Automatic cache management: L1, L2, L3 cache 사이에 움직이는 것은 하드웨어가 처리한다.
• Automatic demand paging: 만약 프로그램이 DRAM에 없는 메모리를 access하려고 할 경우 paging이 일어난다. OS가 자동으로 필요한 page를 memory로 로딩한다.

Memory Hierarchy with a 5-stage pipeline

• L1 cache에 대해서는 I-cache랑 D-cache를 분리

• L2, L3, DRAM에 대해서는 unified 형태

cf. Cache Hierachy: CPU에 가까울수록 high (ex. L1 cache)

SRAM/DRAM:

SRAM (static random access memory)- 접근 속도가

Hierarchical Performance Analysis

각 memory hierarchy level에서의 access time이 t_i이라고 하자.

Ti=hi⋅ti+mi⋅(ti+Ti+1)

• hi: hit rate, 이 때 access time: ti
• mi: miss rate, 이 때 access time: ti+Ti+1

Cache as Request Filter

BR: Bandwidth requested

BP: Bandwidth provided

각각의 cache level을 일종의 필터처럼 생각할 수가 있다.

Hierarchy Design Considerations

1. DRAM (Dynamic RAM)

• used for large memory
• optimized for Capacity/$

1. SRAM (Static RAM)

• Static RAM, cache나 register file에 사용된다.
• Capacity, latency, Capacity/$ 등 다양한 compromise를 고려
• Working set: 어떤 process에서 현재 사용하고 있는 데이터

Cache design basics

Cache interface

Basic operation: cache는 어떻게 작동하는가?

1. Address가 주어지면, cache에서 그 address를 찾는다
2. Hit → data를 리턴한다
3. Miss → Cache에 저장할 새로운 주소를 정한다
4. Update cache

Basic Cache Parameters

• M-bit address: Address space의 전체 크기 (ex. 4GB address space라면 32-bit)
• C (capacity): cache의 총 데이터 사이즈 (ex. 16KB = 2^16 bits)
• G = 2g (granularity): 한 번에 몇 byte를 가져올 것인가? (4 bytes per word)

Direct-mapped cache

• Tag bank: 주소 중에서 tag 비트를 저장한다.
• Data bank: 실제 데이터를 저장하는 역할 (각 줄당 G bytes)
• Valid bit: cache에 있는 데이터가 초기화된 상태인지 확인

m-bit의 주소를 다음과 같이 나눈다.

• idx: 특정 cache block 선택
• tag: cache hit인지 아닌지 확인
• bo (block offset): 만약 hit이라면, 해당 block 안에서 가져올 byte를 선택
• g: 요청한 byte 수 (ex. lw: 4byte)

Cache hit logic

1. Address에서 index를 확인해서 맞는 line을 찾는다.
2. address에 있는 tag와 tag bank에 있는 tag를 비교한다.
3. valid bit를 확인한다 (dirty, 즉 데이터가 초기화되지 않은 상태이면 안 되기 때문에)

→ 이 모든 게 다 맞으면 cache hit이다!

용어 정리를 하고 가자

• page: virtual memory system에 있는, 고정된 사이즈의 memory block.
• cache block/line: CPU가 cache하는 데이터의 단위.
• set: 같은 index를 가지는 cache block/line들의 모임.

Block size & Tag storage overhead

Block size가 작을 경우 tag space를 쓸데없이 낭비하게 된다.

Block size를 늘리면 어떻게 될까?

아래 그림의 cache 에서, 1 row = 1 cache block = 1 cache line

가로 길이가 block size, 세로 길이가 block의 개수라고 생각하면 된다.

오른쪽과 같이 block size를 늘리게 되면 한 번에 가져오는 data가 더 많아진다고 생각하면 됨.

따라서 tag가 전체 cache에서 차지하는 공간이 적어지게 된다.

• tag: 현재 cache에 있는 address
• idx: cache 안에서의 line number를 선택
• bo (block offset): block 안에서 단어를 선택
• g: granularity (byte offset inside word)

Block size and miss rate

block size를 늘릴 때의 장점 (Total capacity C가 고정되어 있을 때)

• Spatial locality가 올라감 (한 번에 multi-word block을 fetch한다는 거 자체가 주변 block까지 가져온다는 뜻이기 때문에)
• Miss penalty는 block당 발생하기 때문에 페널티가 줄어들게 됨
• tag overhead 감소

block size를 늘릴 때의 단점:

• capacity 낭비
• latency 증가 (아래 써있음)
• block수가 줄어들기 때문에 cache 내부에서 conflict가 발생할 가능성이 올라감

Block size and Ti+1 (total access time)

• block이 커지면 loading time도 늘어남 (예를 들어 block의 맨 끝에 있는 단어를 load해야 될 경우 그 block 전체가 loading 될 때까지 기다려야 함!)
• 이를 해결하기 위한 2가지 방법이 있음

Conflicts in direct-mapped cache

= direct-mapped cache에서는 필연적으로 conflict miss가 발생하게 된다!

다음과 같은 Direct mapped cache 그림을 다시 생각해 보자. address가 다르더라도 index가 같으면 같은 cache block으로 매핑되게 된다.

예를 들어, cache size C = 16KB = 2^14 B 이고 block size B = 64B 라고 생각해보면 index는 log_2^C/B = 256개가 된다. 따라서 256번째 memory block마다 collision이 일어난다.

Set-associative cache

📌 Key Point

• Direct-mapped cache는 하나의 index당 저장할 수 있는 위치가 하나만 존재해서 conflict가 일어나게 된다.
• 그렇다면 여러 개의 direct-mapped cache를 묶어서 쓰면 하나의 index가 여러 위치에 저장되어, collision을 최소화할 수 있지 않을까?

📌 기본적인 구조

• Cache를 ”set”으로 나눠서, 각각의 set는 a개의 cache line으로 구성되어 있다.
• 하나의 index가 하나의 set으로 매핑되는데, 각각의 set 안에서는 a개 중 어디에나 들어갈 수 있게 된다.
• set당 여러 개의 line으로 매핑된다

Replacement policy for set-associative cache

LRU (Least Recently Used): 제일 나중에 쓰던 memory block부터 제거한다

Fully associative cache

Block 개수가 C/B개인 cache이다.

각 row마다 tag, valid bit, data가 존재한다.

주소가 주어지면 모든 block에서 tag를 비교해서, 맞으면 hit,

저 삼각형 모양들이 사실 하나의 큰 mux이며, C/B개의 cache line이 input이고 tag 일치 여부 && valid bit 이 control signal이다.

Fully associative cache의 특징

• C/B - way associative cache와 같다.
• CAM = Content-Addressable Memory이다.

시험 문제 풀이

A. How many bits are required for a tag for a cache line in this cache?

sol) tag / idx / offset로 비트를 나눌 수 있다.

cache line이 16 bytes → offset = 4 bits

Cache size = # of sets * line size * associativity 에서

64 = ? * 16 * 2 , # of sets = 2

so, index: 1 bit

tag = 16-4-1 = 11 bits

offset: 32-11-1=20

B. What is the total storage overhead per cache line other than the tag bits?

Storage overhead: 전체 cache 안에서 tag bits가 차지하는 byte 수

valid bit 1 bit + dirty bit 1 bit + LRU bit 0.5 bit = 2.5bits

total 128 bits → 2.5/128

• Total cache size = C, block size = B, associativity = a
• Number of sets = C / (B × a)
• Tag, index, offset 계산:

1. How many copies of the same data can exist in the cache due to the synonym problem?

• Page offset = 12 bits
• cache size = block size * cache sets * set associativity
• block offset = 6 bits
• 따라서 cache lookup에 필요한 총 bit 수는 9(index)+6(offset) = 15 bits이다.
• 그러나 page offset은 12 bits이므로, 2^3 =8개의 synonym이 발생하게 된다.

14. Memory Hierarchy 2

Classification of cache misses

→ Cold, Capacity, Conflict miss!

1. Cold miss

• 어떤 address를 처음으로 access할 때 발생하는 miss
• 어쩔 수 없이 일어난다는 의미에서 compulsory miss라고도 부른다.
• Domination: Locality가 적을 때 (여기저기서 불규칙적으로 access할 때)

1. Capacity miss

• cache size가 data size보다 작을 때
• Domination: C (Cache capacity) < W (Working set size) 일 때 (Cache size가 작은 거)

1. Conflict miss

• Direct-mapped, set-associative cache에서 collision에 의해 miss가 날 때
• Domination: C (Cache size) ≈ W (Working set size)일 때, C/B (같은 건 아니지만 associativity)가 작을 때

Cache read/write (issues)

• Read access: tag, data bank에 동시에 접근
• Write access: tag bank에 먼저 접근하고, write-hit인 경우에만
• 문제: Partial-word write

Store buffer

• Tag bank → data bank 이렇게 순차적으로 접근하면 Store가 여러 cycle 걸리는데, 다음 instruction도 memory instruction이면 structural hazard 발생
• Store buffer:
• Memory forwarding: 같은 address에서 load했을 때 업데이트되기 전의 데이터를 보면 안 되기 때문에, store buffer를 먼저 확인하고 load해서 RAW correctness를 보장한다.

Blocking vs non-blocking cache

• Blocking cache: Cache miss가 발생했을 때 CPU가 완전히 stall
• Non-blocking cache: Cache miss가 발생해도 다른 instruction을 계속 실행.

MSHR (Miss Status Handling Register)

non-blocking cache에서 사용하는 방법

말 그대로 miss인 cache register를 트래킹하는 것을 의미한다.

각 MSHR의 구성은 다음과 같다.

• block address: 어느 cache line이 fetch되고 있는가?
• list of pending loads: dest register, format (byte/word, signed/unsigned), block offset

1. Cache miss 발생 → 새로운 MSHR를 할당 (primary miss), 다른 instruction들은 정상적으로 실행
2. 새로운 cache miss 발생
3. 더 이상 할당할 MSHR entry가 없을 경우 pipeline을 stall한다.

Write-hit / Write-miss policy

데이터를 memory에 store하려고 할 때, write할 주소가 이미 cache에 있으면 Write-hit, 없으면 Write-miss이다.

Write hit: write-back or write-through?

Write-back: Cache에만 쓰고 “Dirty” bit로 지정한 후, 나중에 write back을 한다.

• Dirty: cache에서는 update되었는데 main memory에서는 아직 update되지 않은 것을 의미.
• Dirty가 아니면 write-back을 할 필요가 없음
• L1 cache와 같이 낮은 hierarchy에서 필요한 bandwidth를 줄일 수 있다. (MB/s)

Write-through: Cache에도 쓰고, 아래 레벨에 있는 cache와 memory 등에 모두 쓴다. (ex. L1 cache에서 write hit이 발생했으면 L2, L3를 거쳐서 순차적으로 main memory까지 모두 update한다)

Write miss: write-alloc or write no-alloc?

Write-allocate: Block을 cache에 load한 후에 update한다.

• temporal locality를 활용할 수 있다. (근처에 있는 address를 load할 경우 미리 cache에 로딩을 해놨기 때문에)

Write no-allocate: Block을 cache가 아닌, lower-level memory에 직접 쓴다.

• store와 load 사이에 locality가 높지 않을 경우 굳이 그 데이터를 cache에다가 저장해놓을 필요가 없어서 효율적일 수 있다.

cf. C/B effect: Cache size/block size 의미로

Design tradeoffs

Hierarchy가 높을수록 (ex. L1 cache)

• C는 작아진다 (capacity): 안에 들어 있는 SRAM에 따라 access time이 결정되기 때문에 규모가 작아야 한다
• B는 작아진다 (block size): spatial locality, C/B (cache block)의 개수에 영향을 받음
• a: 적당히

Hierarchy가 낮을수록 (ex. LLC cache)

• C, B가 커진다

Inclusive vs Exclusive cache

LLC (last level cache)

Inclusive cache

• L1에 있는 block이라면 L2, L3에도 있다.
• 문제점: Back invalidation: LLC에서 evict되면 모든 다른 upper level cache에서도 evict 된다.

Exclusive cache

• 문제점: 예를 들어, L1에서 cache miss → LLC까지 cache miss가 났을 때, inclusive cache는 바로 DRAM access하면 되지만 Exclusive cache는 다른 L1도 확인해봐야 함.

Compare: Fully connected layer

지금까지 우리가 봤던 layer들은 fully connected layer이다.

32x32x3 image가 있다고 가정하자. (보통 3차원 이미지라함은 2차원 평면에 있고 컬러 이미지의 경우 R, G, B여서 깊이가 3인 것으로 많이 본다) 그러면 우리는 지금까지 이 image를 3072x1로 납작하게 바꾼 후에 weight를 곱해 왔다.

이렇게 되면 사진 전체의 내용을 고려해줘야 한다. 여기에는 단점이 2가지가 있는데

1. 이미지 전체를 다 계산해야 하므로 계산량이 많아진다.

2. 이미지 내에서 관계없는 내용까지 학습되게 된다. (예를 들어서 동물을 분류하는 classifier를 만들고 싶을 때 고양이 뒤에 있는 배경은 전혀 중요하지 않지만 함께 학습되게 된다.

이러한 문제점들을 해결하기 위해서 나온 것이 convolutional neural network (CNN)인 것이다!

Convolutional layer의 가장 큰 차이점은, 차원을 보존한다는 것이다.

작은 필터를 (ex. 5x5x3) 이용해서 주어진 spatial location에 대해서 그 filter에 해당하는 element에 대한 dot product를 해주는 것이다. sliding하면서 지나가는 것 같은 이 과정을 convolving이라고 한다. (포스텍 23학번 일반전형 면접 문제에 나왔기 때문에 나에게는 제법 익숙한 내용이다. 그만큼 고등학생도 이해할 수 있다는 뜻이라고 할 수 있다) 마치 사진을 스윽 스캔하는 사람의 눈 같은 느낌이다.

Convolution 필터의 깊이는 항상 이미지의 깊이와 같아야 한다.

dot product한 결과에 해당하는 행렬을 activation map이라고 한다. activation map의 개수는 filter의 개수와 같다.

각 layer마다 여러 개의 filter가 있ㄷ고 이 filter가 activation map을 만든다.

ConvNet

ConvNet은 Convolution layer들의 sequence이며, 이 사이사이에 activation function이 들어가게 된다. 

아니

참고로 쓸데없는 지식을 좀 자랑해 보자면 저 사진은 VGGNet의 모습이다. VGG-16은 16개의 layer를 쌓았다는 뜻이고 Conv3_2라고 써 있는 건 3번째 레이어의 2번째 필터라는 뜻이다. 

여러 개의 filter를 쌓을 때는 hierarchy가 있는데, 덜 복잡한 것부터 (low-level이라고 부른다) 쌓아 올린다. 순차적으로 앞에 있는 layer들은 Low-level feature부터 학습하고 (edges), Mid-level features (corner, blob) 등을 학습하다가 점차 high-level features (실제 이미지에 가까운 것)을 학습하는 것을 볼 수 있다. 

왜 이러한 구조가 되어야만 하는지는 직관적으로 생각해보면 쉬운데, 처음에 사진의 아주 작은 영역에 filter를 convolve해봤자 픽셀 자체가 몇 개 없어서 정보가 많이 없기 때문이다. 이후에 배울 pooling과 stacking을 이용하면 점차 복잡한 정보도 이해할 수 있게 된다.

Convolution 식

input image를 여러 layer에 통과시킨다.

conv layer → nonlinear layer (ex. ReLU) → conv layer → pooling

So how does it work?

image에 filter를 activation map를 만드는 일을 정확히 어떻게 하는 것인가?

보통은 7x7 input에서 3x3 filter를 움직이게 된다면, 5x5 output이 나오게 된다. 

stride: 한 번에 몇 칸씩 움직일 것인가

Output size = (N-F) / stride + 1

Padding

Convolution filter가 사진을 픽셀 단위로 지나가다 보면, 모서리에 있는 픽셀들은 학습에 많이 이용되지 못한다는 한계점이 있다.

따라서 0으로 된 테두리를 추가해주게 된다. pad가 이 두께를 의미한다.

또한 padding을 이용하면 convolution의 output의 크기가 줄어들지 않는다는 장점이 있다. 

Number of parameters in the layer?

5*5*3 + 1 = 76

76*10 = 760 layers

Summary

Convolutional layer의 input volume은 3개의 layer로 이루어져 있다.

$W_1$: input width

$H_1$: input height

$D_1$: input depth (ex. RGB로 이루어진 그림이면 depth = 3)

Hyperparameter는 다음과 같다.

1. K: filter의 개수 ( = output depth)
2. F: Filter size (ex. 3x3 filter이면 F=3)
3. S: stride (한 번에 filter가 얼마나 움직이는가?)
4. P: padding (zero layer들을 얼마나 붙여뒀는가)

Output volume

$W_2 \times H_2 \times D_2$

$D_2 = K$, 각 필터가 하나의 output slice를 만든다.

$W_2 = \lfloor \frac{W_1-F+2P}{S}\rfloor+1$

$H_2 = \lfloor \frac{H_1-F+2P}{S}\rfloor+1$

• program마다 다른 거임.
• Average ILP = program 전체의 instruction 수 / PE (processing element)가 무한히 많다고 가정했을 때 필요한 개수
• parallel하게 실행이 가능한 프로그램일수록 값이 커짐

그럼 ILP를 cpu 내에서 어떻게 구현할 수 있을까?

Superpipelined machine

pipeline의 개수를 n개로 늘린다.

Superscalar machine

여러 개의 instruction을 동시에 실행한다.

Operation latency

하나의 instruction이 모든 pipeline stage를 통과하는 데 걸리는 시간

Issuing rate (= 이론적인 IPC)

한 Clock cycle당 Instruction이 얼마나 많이 실행될 수 있는가

ex. 4-way superscalar processor: 4 instructions per clock cycle

Superscalar/Superpipelined degree

Superscalar degree: N개의 머신이 패러렐하게 돌고 있다

Superpipelined degree: M개의 스테이지로 파이프라인 되어 있다

Out-of-Order execution

In-order pipeline의 문제점

Instruction 간의 dependency 때문에 parallelism이 일정 수준을 넘어가고 나면 성능이 급격하게 떨어진다. (forwarding으로도 해결이 안 된다)

• ex. N개의 superscalar로 여러 개를 동시에 실행하고 이를 M개로 pipelining했는데, 이게 dependent한 instruction 간의 거리보다 커진다면? 문제가 되겠죠

Register renaming

• 만약 register가 무한히 많았다면 WAR (anti-dependency), WAW(Output dependency) hazard는 발생하지 않는다.
• 왜냐면 register의 이름 때문에 발생하는 거지 data 자체의 true dependency 가 아니기 때문.
• Renaming table로 architectural register를 physical register로 매핑한다. (이 때 physical register는 CPU 밖에서 보이는 것은 아니다)

• When is it safe to remove a binding (i.e., de-allocate a physical register)

OoO example

• independent한 execution이 순서를 바꿔서 (out-of-order 하게) 실행된다.
• 내부적으로만 순서가 바뀌는 것으로 CPU 밖에서 보이면 안 됨.

OoO의 또 다른 장점: hiding memory latency

Cache miss, 특히 LLC(last-level cache)로 갈수록 cache miss가 나면 많은 instruction을 낭비해야 하는데 OoO로 stall을 해결할 수 있음

Typical Out-of-Order CPU structure

• Fetch→ Decode (→ Register renaming) 까지는 다 in-order
• 여러 개의 Execution Unit으로 issue한다.

그렇다면 Instruction을 어떻게 OoO하게 만들까?

Issue queue (ISQ) or Issue buffer

• Instruction에 있는 모든 operand가 준비되었을 때 issue시킨다.
• 예를 들어 내가 방금 p4←result를 완료했다면,

ROB(register) / LSQ (load-store)

ROB (ReOrder Buffer)

• Programmer’s view에서 instruction은 순서대로 실행해야 하므로, 그 순서 (program order)를 저장해서 순서대로 commit되어 필요한 대로 register 값이 변하도록 해준다.

LSQ (load-store queue)

• memory load-store가 순서대로 commit되도록 해주는 것

1. Store
2. Load

OoO에서 branch를 잘못 해버린다면? (Speculative Execution)

• (앞에서도 많이 나왔지만) Control flow는 모든 instruction의 대략 14퍼 정도를 차지. 근데 OoO를 하면 잘못된 branch prediction에 대한 페널티가 매우 커짐.

in-order/speculative state , commit/rewind

• In-order state와 Speculative(추측성) state를 각자 보관한 다음에,
• 맞으면 Commit한다.
• Rewind: 넌 틀렸다. speculative state는 마치 없었던 것철머 롤백한다.

Modern OoO mechanisms

이거까지 해야 되나 싶긴 한데

P6-style execution vs R10k-style exectuion

P6-style(Intel Pentium Pro) : ROB가 physical register file까지 포함

R10k-style (MIPS 어쩌고): ROB는 program order만 저장하고 physical register file이 있음

Branch prediction in superscalar CPUs

• Superscalar machine에서 parallel하게 돌고 있는 branch instruction이 2개인데 둘 다 branch하면,

Instruction vs Thread level parallelism (ILP vs TLP)

비유하자면 ILP: 나 혼자서 멀티태스킹, TLP: 알바를 고용함

ILP (Instruction level Parallelism): 여러 개의 instruction을 하나의 thread에서 execute

add r1, r2, r3     # ← can run
mul r4, r5, r6     # ← can run in parallel with add
sub r7, r1, r8     # ← must wait for add to finish

ILP에서 쓰는 것

• Superscalar execution
• Out-of-order execution,
• Pipelining, Register renaming 등

TLP (Thread level Parallelism): 여러 개의 thread, process를 동시에 돌리는 것

Software에 multiple thread가 있어야 함

TLP에서 쓰는 것

• CMP (multicore CPUs)

CMP (Chip-MultiProcessor)

• 여러 개의 simple core를 하나의 chip에 패킹해서 돌린다.
• 서로 독립적인 thread를 parallel하게 돌린다→ TLP (Thread-level parallelism)
• Workload가 parallelize가 가능할 때는 유용하다
• Transistor의 개수는 proportional하게 늘어나지 않고 기하급수적으로 늘어난다. (throughput을 늘리는 데 요구되는 게 많기 때문이다)

Superscalar vs. CMP (여러 개의 simple core)

직관적으로 이렇게 보면 왜 Pipeline이 더 커도 사용도가 낮은지 알 수 있음.

Interrupt

1. polling: 주기적으로 문제가 생겼나 확인 (마우스의 polling rate 생각하면 쉽다) 근데 overhead가 커서 잘안쓰임
2. interrupt

Synchronous vs Asynchronous interrupt

• Synchronous: 특정 instruction과 관련된 거 (= exceptions)
• Asynchronous: External 요인에 의해 생긴 거 (= Interrupts)
• Syscall/trap: 오직 exception을 위해 존재하는 instruction

Virtualization and Protection

• 최신 OS는 time-shared multiprocessing을 지원한다. 그러나 각각의 user-level process는 독립적이다.
• 즉 각각의 CPU는 자기가 속한 process 말고는 보거나 조작할 수 없다. (Abstraction의 일종이다)
• user-level architecture state만 보이도록 하고, kernel의 shared resource는 안전하게 관리한다.
• OS 차원에서는 user-level에서는 low-level한 것들을 볼 수 없게 막아버리고, user-level process를 분리한다.

Privilege level?

Abstraction의 형태를 보면 된다. (p.7)

User-level state and instructions 아래에는 privileged level이 있다. interrupt에서만 processor가 이 privileged mode에 들어갔다가 나올 수 있게 된다.

이 Interrupt를 구현하려면?

Precise interrupt

• 2개의 instruction 사이에 정확히 들어간 interrupt.
• 이전의 모든 instruction은 완료되었고, 문제가 되는 것 + 그 이후의 instruction은 전혀 실행되지 않았다.
• RISC-V 등에서 지원한다.

• 이렇게 I_3 단계에서 에러가 난다면 바로 handler code가 작동하기 시작한다
• 만약 여러 개의 instruction에서 동시에 에러가 난다면, 앞에서부터 순서대로 처리.

RISC-V Interrupt architecture

RISC-V는 CSR (Control & Status Registers) 기반으로 interrupt를 해결한다.

• SSTATUS (Supervisor Status Register): Interrupt enable/disable
• SEPC (Supervisor Exception Program Counter): 어느 instruction에서 멈췄는지 PC값을 저장하는 레지스터
• SCAUSE (Supervisor Exception Cause Register): Interrupt가 발생한 이유를 저장하는 레지스터

이 register들은 우리가 일반적으로 쓰는 user instruction으로는 접근할 수 없고, privileged (kernel) 모드에서만 접근 가능하다

• 하드웨어 차원에서*****(매우 중요) interrupt 관련 정보를 저장한다.

Handling interrupts

2가지 방법이 있다. 직접 정해진 handler address로 점프할 수 있고(direct mode) cause에 따라 handler가 직접 interrept

1. Direct mode(RISC-V): 정해진 interrupt handler address로 점프
2. Vectored interrupt: CSR이 base address를 가지고 있고 원인에 따라서 다른 offset을 더해서 그 handler address로 점프한다

• External (asynchronous) interrupt에서는 외부요인이니까 device-specific handler로 직접 해결하고
• Exception (synchrnous)의 경우

Syscall은 user process에서 kernel-level service로 call을 하는 것이다.

Returning from interrupt

• Software 차원에서 register 값을 restore한다.
• RISC-V에는 SRET이라는 특별한 jump instruction이 존재한다.

Nesting Interrupts / Interrupt priority

하나의 interrupt를 서비스하는 동안 다른 interrupt가 생기는 참사가 발생했을 때 이를 해결해준다.

일반적인 경우

• asynchronous interrupt는 하드웨어에 의해서 자동으로 disable되어야 한다. 왜냐하면, 그렇지 않으면 SEPC/SCAUSE/SSTATUS 등이 그 다음 interrupt에 의해 overwrite 될 수가 있다.
• priority가 높은 순으로 처리한다.

Long-running handlers → nesting이 필요

• interrupt handler가 지나치게 오래 걸릴 경우에는 high-priority event를 우선으로 처리한다.
• SSTATUS에 mask를 설정해서 선택적으로 disable시킬 수가 있다!
• Interrupt의 context를 나타내주는 SEPC, SCAUSE, SSTATUS를 stack(memory)에 저장시켜뒀다가 re-enable한다.
• High-priority source만 re-enable해야 무한루프를 방지할 수 있다.

예시

Exception이 일어난 경우

• PC+4, Branch target 말고도 Exception handler address라는 선택지가 생겨서 이를 선택
• ID Flush, EX Flush: 각 단계에 있는 instruction을 모두 flush해버린다
• EX stage에서는 SCAUSE: Exception이 왜 일어났는지, SEPC: 어느 instruction에서 멈췄는지 를 입력한다.

SCAUSE를 읽어서 어떤 exception인지 파악한다.

SEPC를 읽어서 return할 준비를 한다

마지막으로 SRET을 실행해서 돌아간다

• branch prediction을 할 때는 (ID 단계에서) current PC만 알고 있는 상태에서 예측을 해야 함
• 하지만 비슷한 instruction은 program 내에서 반복적으로 실행되고
• jalr 제외하고 (jalr은 PC←rd+imm 으로 점프하므로)는 다 PC-offset target이 static하게 점프를 함

BTB (Branch Target Buffer) table

next PC에 대한 best guess를 저장해놓는 PC의 table (write back 전에 달려있는 장치라고 생각하면 편할 것 같다)

ALU/LD/ST: PC+4

Branch/JAL: PC+offset

JALR: 몰루

여기서 Branch는 항상 taken으로 가정한다

• 그러나 저 맨 위의 그림처럼 PC 전체를 BTB에 쳐넣는 방식으로 구현하면, PC가 32비트라고 쳤을 때 2^32개의 entry가 생기는 참사가 일어난다.
• 따라서 hashing을 통해 2^N짜리 entry table에다가 넣을 것이다. 그러나 BTB가 작을수록collision이 더 많이 생긴다. (서로 다른 PC값이 똑같은 데에 mapping된다)

• 오른쪽 그림과 같이
• instruction fetch 시에 index bit로 BTB entry를 찾고, tag가 맞으면 stored prediction을 쓰고 안 맞으면 무시하고 PC+4를 쓰면 된다.
• Branch/Jump만 저장한다. (대부분의 instruction은 PC+4만 쓰기 때문에)

PHT: Pattern History Table

• 이제 여기에 한술 더 떠서, branch가 직전에 일어났는지 아닌지의 pattern을 저장해놓는 Pattern History Table을 만든다.
• tag가 맞고 직전에 take branch 했어야 branch한다.

2-Bit saturation counter vs hysteresis counter

Saturation: taken으로 prediction했는데 not taken이면→ weakly not taken

Hysteresis: taken으로 prediction했는데 not taken이면→ strongly not taken (틀린 것에 대한 페널티가 크다)

“Gshare” branch prediction

Global Path History를 기반으로 한다.

branch의 결과가 직전의 branch에 영향을 받는 경우가 많음. if/elif/else 이런 생각만 해봐도ㅇㅇ

• BHSR (Branch History Shift Register)에 직전의 branch 결과들을 넣어둔다
• PC bit와 이 값들을 xor 해서 Pattern History Table(PHT)를 만든다 (XOR indexing)

2-level Direction Predictors

기본적인 원리

1. BHT (Branch History Table): 제일 최근 k개의 outcome을 저장해 놓는다
2. PHT (Pattern History Table): BHT의 패턴을 index로 사용해서, Prediction state를 구한다

2-level Direction Predictor의 종류: GAg, GAp, PAg, PAp

table을 채울 수 있는 방법이 크게 3가지가 있음. G: global, S: per-set, P: per-address

Branch history table은 대문자, Pattern history table은 소문자로 표기

A: adaptive

그림 보고 대강 이해하도록 하자

Alpha 21264 tournament predictor

PAg에서의 local history와 GAg에서의 global history를 합친 이런 모델도 있다는 거 정도만 알아두면 됨.

Branch predictor in a pipeline / Speculative Execution Summary

• 일단 믿고 가되, prediction이 틀렸을 때는 younger instruction은 전부 flush해버려야 한다
• BTB와 PHT는 그래서 언제 어떻게 update하는가?
• nextPC가 맞으면 → PHT만 업데이트하면 된다. (아까 봤던 2-level direction predictor fsm에서 strongly taken)
• nextPC가 틀리면? → PHT와 BTB를 둘 다 update해야 한다. history buffer에 prediction된 값을 저장해놓고 있기 때문에, 이제 이게 틀렸기 때문에 update를 해줘야 하는 것

— 여기까지의 얘기는 branch/jump 등에만 해당 —

Return address stack → jalr에서 사용

jalr 같은 register 기반의 jump는 jump할 대상이 어디일지 모름, locality가 적어서 BTB 사용 불가능

보통 일반적으로 risc-v 코드에서 function으로 뛸 때

• jal x0 x1 (x1에다가 내가 어디로 돌아올지 저장해놓고 뜀)
• jalr x0 (돌아올 때 뛴다)

이런

• jal rd imm instruction이 실행되면 PC+4 (return address)를 Return address stack(RAS)에 저장
• 그 다음에 jalr instruction이 실행되면 이걸 pop해서 return jump가 이루어지도록 한다.
• 따라서 사실상 jalr은 branch prediction이 없다.

BTB와 RAS의 차이점? (언제 어떤 것을 써야 하는가)

jalr 과 같은 return instruction의 경우 RAS를 써야 함

같은 return instruction을 쉐어하는 call이 많기 때문에 BTB aliasing이 일어난다 (branch를 어디로 갈지가 overwrite된다)

여기부터는 개념적인 것만 대충 알고 있으면 된다고 함

Trace caching

Trace: 미리 decode된 instruction들의 sequence

• Multi-block fetch: 핵심은 한 블럭씩 fetch하지 말고 미리 decode된 여러 개의 instruction (”trace”)를 fetch하자는 것이다.
• 단점으로는 (gpt 피셜) 더 많은 cache space가 필요하고 하드웨어가 복잡해진다.

Intel Pentium4 Cache

자 그래서 Intel Pentium4 Cache는 어떻게 x86 instruction을 디코딩할까? 지금부터 알아보자

1. Instruction Length Decoder (ILD):

• x86 instruction은 길이가 variable하니까 길이를 정해준다

2. Dynamic Translation:

• x86 instruction → uops (micro-operations)으로 변환해준다. 복잡할수록 uops의 길이가 길어지고, microcontroller 같은 걸 이용할수도 있다

Predicted execution: If-conversion

ex. Intel Itanium에는 “predication”이라는 게 있다

• 각 instruction에 predicate bit가 있다. control flow를 data flow로 만드는 것인데 branch를 없애버리고 통째로 돌린다? 같은 느낌

Software로 branch prediction의 성능을 개선시키는 방법

1. static branch hints: taken일지 not taken일지 instruction encoding에다가 집어넣음
2. Branch prediction(brp)라는 instruction이 있어서 branch execution 전에 BTB나 PHT state를 미리 정할 수가 있음
3. TAR (Target address register): BTB (fully-associative) 음 쓰기 귀찮다

요약

Direction Prediction vs Target Prediction

• Direction prediction: branch or not branch?
• Target prediction: Where will the branch go if it is taken?
• BTB+RAS를 이용하면 target prediction (branch/jal)은 거의 정확하게 가능하다.
• 그러나 taken vs not taken을 아는 건 결코 쉬운 일이 아니다.
• 90% backward branch (loop)는 taken이고
• 50% forward branch (if-statement)는 taken이다.

Performance & Cost Model

pipelining 사이사이에 delay T가 있을 때 throughput = 1/(T+S) where S=latch delay

k단계로 pipeline했다고 생각해보자.

Throughput = 1 / (T/k+S)

Cost = G + L*k (G: combinational logic 전체의 cost, L: gate의 개수)

따라서 Cost-performance tradeoff라는 것이 존재한다. 미분해서 C/P의 최소값을 구해보면

k_opt = \sqrt(GT/LS) 이렇게 됨

Pipelining with Pipeline registers installed

이렇게 각 단계 사이에 register를 설치해준다.

진행되는 방식은 slide 보면 나오니까 생략

Control for pipelining

Pipelining을 하면 Control signal 또한 pipeline되어 있어야 한다. (정확한 타이밍에 0/1값이 정해져 있어야 하기 때문에)

2가지 방법이 있는데

1. single-cycle이랑 똑같이 Instruction decode단계에서 decode하고 control signal들을 buffer한다.
2. Instruction field (opcode, funct3, funct7) 등을 pipeline에다가 집어넣고 EX, MEM, WB 등을 통해 decode 해 준다.

사진 속 방법이 1번과 같은 방법이다.

그러나 현실적으로 pipelining에는 여러 가지 문제가 있는데…

Data hazards in pipelining

8단원

• True Dependency (RAW - Read After Write)
• Anti Dependency (WAR - Write After Read)
• Output Dependency (WAW - Write After Write)

뒤에서 Hazard의 종류는 더 정리해서 보도록 하자

Pipeline stall

PCWrite 랑 IF/ID.Write 를 disable시켜서 PC가 새로운 instruction을 fetch하도록 한다.

RegWriteID 와 MemWriteID도 disable시킨다

Impact of stall on performance

Average IPC with stall: N/(N+S) when there are N instructions and S stall cycles

Data forwarding

Computational result를 가져와서 data를 forwarding하는 것

lw instruction 같은 경우, 실제로 data를 produce하는 건 memory에서 read할 때기 때문에 forwarding을 사용해도 stall이 하나 필요함. 이걸 load-use hazard라고 한다

lw x2 20(x1)
and x4 x2 x5

이거 빼면 웬만한 data hazard는 forwarding으로 stall 없이 해결할 수 있다.

Code scheduling

컴파일러가 자체적으로 코드 순서를 바꿔서 lw 직후에 그 값을 사용하지 않도록 하는 것

Superpipelining

각 단계를 더 짧게 만들어서 clock cycle을 줄이고 throughput을 올리고자 하는 접근.

그런데 문제는

• pipeline hazard의 개수를 늘린다 (stage 자체가 여러 개가 되니까)
• data forwarding과 hazard detection을 더 복잡하게 만든다

Control hazard

9단원

일단 대부분의 경우 branch를 하니까, 할거라고 일단 예측을 한다.

안 할 경우 pipeline을 flush 해버린다 (NOPs, PC assumption)

ALU execution이 되고 나서야 branch가 taken인지, not taken인지 알 수 있다.

IPC: branch prediction을 얼마나 잘했는지 판단하는 지표로 사용된다.

IPC = 1 / (1 + branch prediction을 잘못할 확률 * 잘못된 guess에 대한 penalty)

1. 일반적인 경우

recall) IF → ID → EX → MEM → WB

beq x1 x0 16 에서 PC+16 값이 PC로 WB 될 때까지 3개의 bubble이 필요하기 때문에

그림과 같이 3개의 cycle이 낭비된다.

2. EX stage에서 비교연산과 동시에 계산해버린다

branch의 경우를 생각해 보자.

• PC use는 IF 단계에서, PC produce (next PC) 는 EX stage에서 비교연산을 함과 동시에 produce된다.
• 원래는 MEM 단계까지 기다려야 했었는데, EX 단계에서 branch condition 및 branch target address를 계산한다.
• 20%가 branch instruction이고 70%가 branch taken일 때,

이렇게 훨씬 향상된 성과를 보여준다!

ID stage에 comparator를 만들어서 branch를 미리 해결하면, 잘못 take한 branch에 대한 페널티를 1 cycle까지 줄일 수 있음.

3. ID stage에서 해결한다

• beq와 같이 register 값만 알아도 branch 여부를 알 수 있는 instruction의 경우 ID stage에서 해결하는 것도 가능하다. 즉, PC use: IF / PC produce: ID
• ID stage에서 comparator를 추가하여 branch condition인지 아닌지를 판별한다.

그림을 보면

• x1, x2를 register read한 후에 ID 단계에서 comparator가 작동해서, 같으면 branch taken.
• Compute target address: immgen block에서 offset을 바로 generate하고, offset<<1을 current PC에 더해서 target PC를 계산한다.
• 만약에 prediction이 잘못되면, flush해버린다

Hazard detection unit

branch instruction이 writeback이 아직 되지 않은 value에 depend하는지 확인한다. 예를들어

add x1 x2 x3
beq x1 x0 label

(잘 보면 data forwarding unit도 있음)

요약: Hazard의 종류

1. Control hazard (9단원)
2. Structural hazard (7단원)

PVS (Programmer Visible State)

PC, register file, Instruction memory, Data Memory

자세한 설명은 아니까 패스

Combinational read, synchronous write

• Combinational read: register file 안에 있는 컨텐츠와 read select port에 따라서 읽는 것이기 때문에 combinational하게 처리 가능
• Synchronous write: read output에 영향을 주지 않도록 (race condition이 안 생기도록 한다)

Instruction Processing

1. IF (Instruction Fetch): PC에 있는 주소값을 Instruction memory에서 읽어오는 과정
2. ID (Instruction Decode): IMEM에서 읽어온 주소값을 Immgen을 통해 쪼개서 Register에 넣어주는 과정
3. EX (ALU): 연산
4. MEM: Data memory에서 write/read
5. WB: write back (읽은 값을 register에 저장, PC를 update)

Single cycle cpu의 문제점

Single cycle implementation에서는

sequential과 atomic한 ISA semantic으로 적당함.

하지만 모든 instruction이 가장 느린 instruction의 clock cycle을 기준으로 돌기 때문에 비효율적이다.

해결 방법?

1. 일단 50ps로 클락을 돌려
2. 각 instruction의 종류마다 걸리는 시간이 다 다르니까 여러 clock cycle 동안 돌게 하되,

Performance Analysis (그래서 빠르긴 함?)

p.10에 있는 예시

Single cycle clock period: 600ps, multi cycle clock period: 50ps

Multi cycle

IPC

Reducing datapath (ALU) by sequential reuse

(PC ← PC+4) (PC ← PC+imm) (ALU)

IR (Instruction register)

• Memory에서 instruction을 읽기 전에 한 번 keep해둔다

이걸 하기 위해서는 control value가 많이 있어야 됨

Single-cycle에서 썼었던 Control Signal들 (RegWrite, MemRead, MemWrite, MemtoReg)

ex) ADD rd, rs1, rs2

1. Cycle 1: Instruction fetch
2. Cycle 2: Register read
3. Cycle 3: ALU Execution
4. Cycle 4: Write Back

RT sequencing

Register transfer의 줄임말. cpu는 한 번에 오직 하나의 resource만 utilize할 수 있으므로 겹치지않도록 sequencing해주는 게 중요하다. 아래 표가 그 generalization

Microsequencer

• 앞서 말한 RT sequencing을 계산하기 위해서는 control signal이 필요하다. Microsequencer는 control signal을 generate하는 하나의 FSM이라고 볼 수 있다.
• Input: 지금 실행하고 있는 instruction의 opcode와 현재 microstate (ex. IF1, IF2, EX….)
• Output: control signals (ex. ALUSrcA, IRWrite, PCWrite…), next microstate

근데 이거는 정말 비효율적이고 문제가 많은 방법인데

• 2^n 비트의 microstate가 실상 다 사용되는 게 아님

Vertical microcode

ROM의 output으로 k개의 micro-operation (다른 말로 RT, Register Transfer)들을 넣어서 다 미리 저장해놓는 방식이다

ex. “PC ← PC+4”, “PC ← ALUOut”, …

이걸 또 다른 ROM에 연결시켜서 control signal로 번역한다.

k<<m인 경우 (micro-op encoding이 control signal 전체보다 적은 경우) 2^n*m보다 크기를 줄일 수 있게 된다.

Horizontal microcode

각 state 자체를 micro program counter로 생각한다.

address table 대신에 uPC ← uPC + 1 (sequential step)을 통해 next address를 계산

2^(state bits + opcode bits) → 2^uPC bits로 ROM 개수

Input: control signal m개

Output:

Microcoding for CISC

새로운 instruction을 implement해야 할 일이 생겼을 때, Microcontroller와 datapath를 연장해서

Millicode: ISA-level subroutines hard-coded into the ROM

Nanocode: Microcoded system 안에 있는 Microcode(?)

Latency vs Throughput

Latency: task의 시작과 끝까지 걸리는 시간. Shorter latency = higher performance

Throughput: 정해진 시간 동안 끝낼 수 있는 task의 수. job/time

• Concurrent하게 여러 task를 동시에 실행할 수 있는 경우 shorter latency ≠ higher throughput

ex) P&H p.93

1. processor를 더 빠른 버전으로 바꾸면? → execution time(latency)은 빨라지고 throughput도 올라감
2. processor를 여러 개 추가하면? → latency는 그대로지만 throughput은 커짐

Iron law of processor performance

간단히 말해, program을 실행하는 데 걸리는 시간 (Time per program)은

time/cyc * cyc/inst 하면

FLOPs: 새로운 단위. # of floating-point operations / program runtime

Power usage

Power = energy/time

Performance = 1 / Time

Architecture vs Microarchitecture

ISA level: Instruction set manual

software와 hardware 사이의 abstract interface.

• The instruction set (e.g., add, load, branch, ecall)
• Register names and count (e.g., 32 general-purpose registers)
• Data types and sizes (e.g., 32-bit, 64-bit)
• Memory model (byte-addressable, alignment, endianness)
• Calling conventions (how functions pass arguments/return values)
• Privilege levels (user, supervisor modes)
• Exception and interrupt behavior

등을 포함한다.

Microarchitecture level:

• Datapath and control logic unit들이 어떻게 구성되어 있는지
• CPU가 “어떻게” instruction을 실행할 것인가?

예를 들어,

• Superscalar width (1-wide, 4-wide, etc.)
• Out-of-order execution logic
• Register renaming mechanisms
• Branch prediction units
• Cache hierarchy and access timings
• Reorder buffer, issue queues, load/store queues
• Clock gating, speculative execution, energy optimization

Architecture가 설계 blueprint라면 microarchitecture는 구체적인 엔지니어링 설계도

ㄴ 아, 좋은 비유네용

Von Neumann Architecture

• 컴퓨터 전체가 하나의 memory space를 중심으로 organize되어 있다.
• Instruction이 Program Counter (PC)가 가리키는 instruction에 따라서 sequential하게 실행된다.
• Program order: 순서가 중요하다.
• Storage locations: 변수가 memory에 저장된다.

Von Neumann vs Dataflow

Dataflow: program counter가 없음.

따라서 실행 순서도 상관이 없음

Programmer Visible State

• CPU 안에서 Programmer가 직접 read, access, modify 할 수 있는 부분들.
• Atomicity of an instruction: PVS에 partial update는 이루어질 수가 없다. (하나의 instruction을 실행하면 반드시 끝까지 실행된다)
• Instruction은 PVS를 변화시킨다.

Early ISA: EDSAC

• Single accumulator architecture: “Accumulator”라는 하나의 GPR만 사용
• Acc, Memory, ALU로 구성
• Address가 instruction에 hard coded되어 있었음
• 문제점?

Evolution of “Register” Architecture

Accumulator만으로는 불충분하다는 걸 알게 됨.

Register indirection: Instruction의 주소 필드가 register를 가리키고 register는 메모리의 operand 주소값을 가지는 것

Operand Sources

다양한 운영체제 간에 어떤 차이가 있는지 외우자!!!

ALU operand가 memory를 직접 access 할 수 있는가?

• Yes: x86, VAX, CISC (Complete Instruction Set Computer)
• No: MIPS/RISC (Reduced Instruction Set Computer)

Instruction의 종류가 얼마나 다양한가?

• MIPS/RISC → x86 → VAX 순으로 갈수록 복잡해짐

Instruction의 길이가 variable한가? (10단원 하다가 나와서)

• Yes: x86 (1-15비트), VAX, CISC
• No: MIPS, RISC-V (4바이트로 고정)

Memory addressing modes

메모리에서 불러오는 데에는 다양한 방법이 있음

(참고로 여기서 rt = register

1. Absolute: load rt, 10000 10000이라는 절대 주소값에 있는 값을 로드한다
2. Register indirect: load rt r_base r_base에 있는 주소에서 load한다. GPR[r_base]를 사용
3. Displaced or based: load rt, 10000 offset + GPR[r_base]를 address로 사용
4. Indexed: load rt, (r_base, r_index) GPR[r_base] + GPR[r_index]에 있는 값을 사용
5. Memory Indirect: load rt ((r_base)) r_base에 있는 주소가 가리키는 값을 load
6. Auto inc/decrement: load rt, r_base+ r_base 주소에서 불러오고 자동으로 increment/decrement한다.

ISA를 만들 때 어떤 점을 고려해야 할까

1. Open-ended design: 나중에 시스템이 확장되더라도 개선할 수 있도록 해야 한다
2. General purpose:
3. Inter-model compatibility

Lec3 - ISA 2

RISC-V (RV32I) Programmer Visible State

1. Program Counter (현재 instruction을 포함하는 32-bit memory address)
2. GPR (general purpose register file)
3. Memory (byte-addressable)

MIPS 설계 원칙

ㄴ 참고로 MIPS는 Microprocessor without Interlocked Pipelined Stages의 줄임말로

1. Simplicity favors regularity: 간단해지기 위해서 같은 형태를 사용하는 것이 좋다.
2. Smaller is faster: register 및 instruction set의 수가 적을수록 좋음
3. Good design demands good compromises
4. Make the common case fast: 자주 일어나는 연산은 빠르게 해야 한다

ISA format

우선 큰틀은 아래와 같음 (다행히 CS61C에서 배운거임!)

1. R-type: add, sub, mul 등등….

add rd rs1 rs2

교재에서는 register를 general purpose register라는 뜻으로 GPR이라고 쓰지만 나는 편의상 R로 씀

R[rd] <- R[rs1] (연산자) R[rs2]
PC <- PC + 4

연산 종류

• ADD, SUB, AND, OR, XOR << 아는 거
• SLT, SLTU: Set If Less Than
• SLL, SRL, SRA: Shift (Left/Right) (Logical/Arithmetic)

2. I-type: addi, andi, etc. / lui / load (lw, lh, lb, lhu, lbu) / jalr(아래에서..)

addi rd rs1 imm

ex) lw a0 16(s0) : s0 register의 s0+16

lui rd constant : imm 값이 클 때 (32-bit) 사용

imm = immu << 12
R[rd] = imm

lui x19 976
addi x19 x19 1280
// 이러면 976<<12 + 1280의 값을 x19에 넣을수가있음

lw rd imm(rs1)

address <- sign-extend(imm) + R[rs1] // rs1값+imm이 address익
R[rd] <- MEM[address]                // 이 address에 있는 값을 memory에서 읽어와서 rd에 대입
PC <- PC + 4

ex) lw x10 12(x5) 를 실행한다고 생각해보자

 

0x100C에 있는 word 0x12345678 를 x10으로 load한다

Endianness

위와 같이 뒤의 byte가 더 큰 address에 저장되면 little-endian, 반대면 big-endian

RISC-V는 little-endian이다.

Data alignment

word 단위로 깔끔하게 align이 되어 있어야 한다.

RISC-V는 data access에 대해서는 unaligned access도 허용하나, instruction access는 불가.

이 말인즉슨 Instruction은 항상 0x00000000, 0x00000004, 0x00000008, … 이런식으로 word 단위의 address에만 저장되어 있다. 따라서 마지막 2bit는 항상 0이 된다.

3. S-type: sw, sh, sb

address = sign-extend(imm) + R[rs1] // rs1값+imm이 address익
MEM[address] <- R[rd]               // 이 address에 있는 값을 memory에서 읽어와서 rd에 대입
PC <- PC+4

sw a0 12(a1)

R[a1]+12의 address에다가 a0의 값을 저장

store opcode = 0100011

코딩예시)

4. SB-type (branch instructions)

Conditional branch instructions

imm[12|10:5]

imm[0]=0이라서 생략한다. (branch는 언제나 even address로만 하기 때문이다)

beq rs1 rs2 imm beq, bne, blt, bge, bltu, bgeu

Copy

beq x22 x23 then
sub x19 x20 x21
beq x0 x0 exit
then:
	add x19 x20 x21
exit:

5. J-type (jump instructions): jal

jal vs jalr 비교 (중요)

jal rd, imm (jump and link!)

내가 RISC-V 코드를 실행하다가 어떤 함수로 뛰고 싶을 때 주로 사용한다.

기존의 return address를 register에 저장해놓고, PC+imm 만큼 뛴다. 따라서

R[rd] <- PC + 4
PC <- PC + imm

jalr rd imm(rs1)

R[rd] <- PC + 4
PC <- (R[rs1] + imm) & 0xFFFFFFFE // lowest bit를 0으로 만든다

Caller에 return할 때에 주로 사용

jalr x0 0(x1): R[x1] 에 있는 값을 PC로 리턴하고 return address는 0으로 만든다 (즉, 저장하지 않는다)

Conditional jump (jalr x0 label) 할 때도 사용됨

Caller-saved vs callee-saved register

어떤 function (callee) 이 다른 function(caller)에 의해서 call 될 때를 생각해 보자

caller_func:
		callee_func

Callee-saved register = call을 어떻게 하든 callee가 변하지 않도록 리턴해준다

• s0 (frame pointer) ~s11 (x8, x9, x18-x27), sp (stack pointer)

Caller-saved register = callee가 저장하지 않아도 되기 때문에 값이 변할 수 있음

• ra (return address, x1), t0-t6, a0-a??
• argument, temporary values, return value 등을 패싱할 때 사용

Calling convention

이를 바탕으로 생겨난 게 calling convention이다.

main (caller function에서는 caller-saved register만 저장해주면 된다.)

# Prologue
# 1. Caller-saved register를 저장한다
addi t0 x0 5
addi t1 x0 10

# Stack space를 allocate 한다(sp가 있는 주소에 store한다) 
addi sp sp -8
sw t0 0(sp)
sw t1 4(sp)
sw ra 8(sp)

# 2. caller loads arguments into a0~a7 (x10~x17)
mv a0 t0
mv a1 t1

# 3. caller jumps to callee using JAL x1
jal ra sum   

# Restore caller
lw a1 0(sp)
lw ra 4(sp)
addi sp sp 8
jalr x0 x1

sum (마찬가지로 callee에서도 callee-saved register를 저장해둔다)

sum:
    addi sp, sp, -8         # Step 4: allocate stack frame
    sw   s0, 0(sp)          # Step 5: save callee-saved register s0

    mv   s0, a0             # use s0 to save a0 (optional, demo only)

    add  a0, a0, a1         # Step 6: compute sum → result in a0

    lw   s0, 0(sp)          # Step 7: restore s0
    addi sp, sp, 8          # deallocate stack frame

    jalr x0 x1              # Step 8: return to caller (JALR x0, x1 style)

Memory usage convention

• 기본적으로 stack space는 local variable들을 보관하며, high address에 보관되어 있고 PC/program code 등은 text의 영역에 있어서 low address에 보관되어 있음.
• text 위에 global variables (static data), heap(dynamic data, malloc)이 있고 free space로 커져 나가는 느낌이다.

최종 요약.

그리고 gradient를 계산하는 방법으로는 analytic gradient(직접 미분)과 numerical gradient(f(x+h)-f(x-h)/2h로 계산) 방법이 있다. 보통 코딩할 때는 numerical gradient를 더 많이 쓴다.

Computational graph를 이용하면 복잡한 함수를 간단하게 나타낼 수 있게 된다. 특히 CNN 등의 network에서는 복잡한 함수들이 많기 떄문에 도움이 된다.

Backpropagation

backpropagation은 간단하게 설명하면 chain rule을 연속해서 적용시키는 것이다.

A simple example

f라는 함수에 대한 x의 영향을 알고 싶다고 할 때, backprop의 핵심은 local gradient만 계산하면 전채 gradient를 알 수 있다는 것이다.

chain rule을 생각하면 너무나도 당연한 결과이기 때문에 이게 뭐가 특별하냐고 생각할 수도 있겠지만, 이후에 이 아이디어를 통해 복잡한 함수를 간단하게 나타낼 수 있다는 것을 알게 될 것이다.

Backpropagation은 두 단계로 나눌 수 있는데 forward pass와 backward pass이다.

Forward pass

정상적으로 식의 값을 계산해 나가는 과정이다.

Backward pass

뒤에서부터 순차적으로 식의 gradient를 계산하는 과정이다. local gradient와 upstream gradient의 곱으로 나타낼 수 있다.

다양한 함수들의 gradient

max(x1,x2)의 경우 x1<x2일 때 x1의 gradient는 0, x2의 gradient는 1이다.

직관적으로 계산에 영향을 주는 값만 남는 것이 당연하다.

add gate: gradient distributor 

max gate: gradient router

mul gate: gradient switcher

정도로 볼 수 있겠다.

Backpropagation (vectorized)

실제 머신러닝 데이터를 다룰 때는 대부분 array 또는 벡터 형식으로 된 데이터를 다루게 된다.

따라서 gradient도 자코비안으로 나타나게 된다

이런 식으로 vectorized된 예시에 대해서도 똑같이 계산할 수 있음

Example code

class ComputationalGraph(object):
	def forward(inputs):
    	# 1. pass inputs
        # 2. forward pass
        for gate in self.graph.nodes_topologically_sorted():
        	gate.forward()
        return loss
    def backward():
    	for gate in reversed(self.graph.nodes_topologically_sorted()):
        	gate.backward()
        return inputs_gradients

Neural Networks

linear function은 여러 개 합성해도 결국은 하나의 linear function으로 납작하게 바뀌게 된다.

따라서 score function 계산할 때 non-linearity을 적용시켜주는 게 중요하다. intermediate variable에 non-linear function을 적용해준다. (이건 max, sigmoid, relu, 등등등.... 나중 가서 배우겠지만 많은 것들이 가능하다) 이를 통해서 더 복잡한 non-linear function을 만드는 것이다.

3강에서 Image recognition을 위해 썼던 loss function을 되짚어 보자. weight matrix의 행이 각 input에서 어떤 것을 찾고 있는지에 대한 template 역할을 한다.

image recognition에서의 문제점은 template이 하나만 있기 때문에, 한 가지 category를 대표하는 이미지에 가중치를 주고 싶을 때 다양성이 떨어진다. 따라서 layer 개수를 늘리면 더 다양한 template에 대한 가중치를 부여할 수 있게 된다.

예를 들어, 이 식에서

intermediate variable h는 w1에 포함되어 있는지 각 template을 얼만큼 포함하고 있는가에 대한 값이고 

w2는 이 intermediate score을 weighted sum해서 최종적인 class 분류를 하는 것이다.

이렇게 점점 deep한 neural network를 만들 수 있게 된다.

지금 한 번 colab으로 간단한 2-layer neural network를 직접 만들어 보자.

2024 버전 기준으로는 Lecture 2에 포함되어 있지만 따로 분리했음

Multiclass SVM loss:

$(x_i, y_i)$ 예시에서 $x_i$는 image, $y_i$는 integer label, score $s = f(x_i, W)$일 때

$L_i = \sum {j \neq y_i} max(0, s_j - s{y_i} +1) $

Multiclass SVM loss: Example code

def L_i_vectorized(x, y, W):
	scores = W.dot(x)
    margins = np.maximum(0, scores - scores[y] + 1)
    margins[y] = 0
    loss_i = np.sum(margins)
    return loss_i

자 그러면 이러한 경우를 생각해보자.

$ f(x,W) = Wx $

$ L = \frac{1}{N} \sum_{i=1}^N \sum _{j \neq y_i} max(0, f(x_i; W)j -f(x_i;W){y_i}+1) $

ex. L값이 0이 되는 weight W를 찾았을 때, 이 값은 유일한가?

→ No. 2W also has L=0 (achieves zero loss)

Margin between correct and incorrect scores will double. But this means that it still has zero loss.

Problem: inconsistency. How is it going to choose between all the W's?

Regularization term

Regularization term이라는 건 왜 필요할까?

training data에 맞춰서 training을 하다 보면 test data에는 맞지 않는 overfitting이 발생할 수 있음 (classifier가 너무 복잡해지게 됨) 따라서 모델을 가능한 simple하게 만드는 것이 중요하다.

Bias-variance tradeoff라는 말이 있다.

Bias: 참값과 추측값의 차이를 의미한다. Training dataset에 대한 예측의 정확도를 의미하기도 한다.

Variance: 주어진 모델을 기반으로 한 prediction들간의 차이를 의미한다. Variance가 클수록 test/validation 데이터에 대한 정확도가 떨어지는 것이라고 볼 수 있다. (high testing/validation error)

regularization term은 bias를 늘리고 variance는 줄인다. 이 regularization을 얼마나 해 줄건지가 $\lambda$ = regularization strength (hyperparameter) 이다.

이게 무슨 말인지 이해가 안 될 수 있는데, 예시를 들어보자. 2차원 평면에 찍혀 있는 2종류의 점들을 분류하는 classifier를 만든다고 생각해보자. 각 점 사이를 모두 연결해서 복잡하게 decision boundary를 만들면 training data에는 완벽하게 맞겠지만 새로운 점이 추가되면 안 맞음!

출처: https://www.geeksforgeeks.org/overfitting-and-regularization-in-ml/

1. L2 regularization = $ R(W) = \sum_{k}^{}\sum_{l}^{}W_{k,l}^{2} $
2. L1 regularization = $ R(W) = \sum_{k}^{}\sum_{l}^{}|W_{k,l}|$
3. Elastic net (L1+L2) = $ R(W) = \sum_{k}^{}\sum_{l}^{} \beta W_{k,l}^{2} + |W_{k,l}| $
4. Max norm, dropout....

"Occam's Razor": 여러 가설 중에 가장 간단한 것이 가장 좋은 것이다 (무슨 12세기의 과학자가 한 말인데 대개 딥러닝에도 적용된다.)

Penalizes the complexity of the model.

ex)

$ x = [1, 1, 1, 1] $

$ w_1 = [1,0,0,0] $

$ w_2 = [0.25, 0.25, 0.25, 0.25] $

L2 regularization: $w_1$ 선호

L1 regularization: $w_2$ 선호

즉, L2 regularization은 큰 weight가 여러 개 있는 것을 선호하고 L1 regularization은 반대로 큰 weight가 하나라도 있는 것에 대해 큰 페널티를 준다고 할 수 있다.

그렇다면 근본적으로 왜 regularization term을 추가하는 것이 모델의 complexity에 영향을 줄까? 엄청 복잡한 10차 함수로 decision boundary를 정했는데 weight 값은 엄청 작을 수도 있는 거 아니냐?라는 의문이 들 수 있다. 경험적으로 regression을 할 때 딱 맞추려면 weight값이 커지는 게 당연하다고 볼 수도 있지만, neural network를 이용해서 조금 직관적으로 그 이유를 알아보자.

W가 0으로 갈수록 hidden layer들은 존재하지 않는 것이나 마찬가지가 될 수 있다.  (왜냐면 각 layer는 wx+b 꼴로 계산되기 때문이다)

따라서 neural network 자체가 단순해지기 때문에 overfitting을 막는 효과가 있다고 한다.

하지만 수학적으로 오버피팅을 완벽하게 정의할 수 있는 방법 자체가 많이 없기 때문에 어쩔 수 없는 것 같기도 하다

Softmax classifier

어떤 값이 주어졌을 때 그 값에다가 exponential 씌우고 normalize하는 함수를 softmax function이라고 한다.

여기서 negative log likelihood를 최소화하는 것이 우리의 목표이다.

Optimization

gradient: 각 차원에서의 partial derivative

slope: dot product of the direction with the gradient

direction of steepest descent is the negative gradient.

아까 봤던 loss function을 적당히 잘 미분하면 analytic gradient를 얻을 수 있다.   

실제로 숫자를 대입해서 numerical gradient를 항상 계산할 필요는 없다는 것이다.

이것이 그 유명한 gradient descent 기법이다. 

가장 단순하게 gradient descent의 코드를 짜보자면 다음과 같은 형태로 나오게 된다

while True:
	weights_grad = evaluate_gradient(loss_fun, data, weights)
    weights += -step_size * weights_grad 		# update parameter

step size는 hyperparameter로, 사실상 gradient descent 기법에서 가장 중요한 것이나 마찬가지이다.

Stochastic gradient descent에 대해 알아보자.

gradient를 계산하는 식은 다음과 같은데, 저 전체 sum을 계산하는 과정이 매우 복잡하므로 minibatch만큼만 계산을 한다.

while True:
	data_batch = sample_training_data(data, 256)
    weights_grad = evaluate_gradient(loss_fun, data_batch, weights)
    weights += -step_size * weights_grad

Input: image → Output: Assign image to one of a fixed set of categories

Challenges in image classification

1. semantic gap

- 사람은 고양이를 보고 직관적으로 고양이라는 것을 알 수가 있음. 하지만 컴퓨터는 눈이 있는게 아니기 때문에 그냥 [0,255]의 값을 가지는 숫자들의 grid라고 픽셀들의 집합 정도로만 생각하게 됨.

- 사람은 똑같은 고양이를 다른 각도에서 찍어도 같은 고양이라는 것을 알아볼 수 있음.

but 컴퓨터 입장에서는 모든 픽셀 값이 바뀌기 떄문에 같은 것이라는 걸 알기가 힘듦

2. intraclass variation (같은 고양이끼리도 종에 따라서 다르게 생겼기 때문에)

3. 고양이를 종별로 구별하고 싶은 경우

4. background clutter (배경색이 같은 경우) Occlusion (detect하고 싶은 물체가 매우 일부분만 보이는 상태라면?)

machine learning: data-driven approach

데이터를 통해 "learn"할 수 있는 알고리즘을 만드는 것이 목표이다.

1. collect a dataset of images and labels
2. use machine learning to train a classifier
3. evaluate the classifier on new images

def train(images, labels)

→ return model

def predict(model, test_images)

→ 앞에서 train한 model을 바탕으로 label prediction

Datasets for image classification

1. MNIST (숫자 쓰는 dataset)

가장 흔한 데이터셋.
10 classes (0-9), 28x28 grayscale
매우 단순한 데이터셋이기 때문에 MNIST에서 high performance를 보여주는 알고리즘이어도 다른 데이터에 대해서는 안 그럴 수가 있음

2. CIFAR10

10 classes, 32x32 RGB images

cs231n 과제에서 사용한다고 함

3. ImageNet

1000 classes, ~1.3M training images

Perfomance metric: top 5 accuracy, 알고리즘이 predict한 5개의 label 중 하나만 맞으면 됨
image classification에서 반드시 좋은 성능을 보여줘야만함

기타) Omniglot: Characters from 50 different alphabets (162 categories)

Only 20 images per category -> few-shot learning 알고리즘을 만들 때 많이 이용

예를 들어 한 번 해보자...

Linear classifier를 실제 코드로 implement하려면 과연 어떻게 해야 하는 것인가...

먼저 image들을 전부 loading시켜 준다.

# Xtr (size 50000 * 32 * 32 * 3) holds all the images in the dataset
# Ytr (1d array of length 50000 holding all the training labels)
Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/')

이미지들을 reshaping을 해서 모든 이미지를 row로 늘인다

Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3)	# Xtr_rows becomes 50000 x 3072
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3)	# Xte_rows becomes 10000 x 3072

다음으로는 classifier를 만들어 준다.

nn = NearestNeighbor()
nn.train(Xtr_rows, Ytr)
Yte_predict = nn.predict(Xte_rows)
print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

First classifier: Nearest neighbor

2개의 이미지가 얼마나 semantically similar한가?
(test image - training image) 픽셀값의 차를 계산한 후 L1 distance를 계산해서 pixel-wise absolute value difference를 구한다.

Nearest neighbor classfier (code)

import numpy as np

class NearestNeighbor:
	def __init__(self):
            pass
        
   	def train(self, X, y):
            *** X is N x D where each row is an example, Y is 1-dimension of size N ***
            # simply memorize all the training data
            self.Xtr = X
            self.Ytr = y
    
   	def predict(self, X):
            num_test = X.shape[0]
            Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
            for i in xrange(num_test):
            # find the nearest training image to the i'th test image using the L1 distance 
                distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
                min_index = np.argmin(distances) # get the index with the smallest distance
                Ypred[i] = self.ytr[min_index] # predict the label of the nearest example
            return Ypred

Q. Nearest Neighbor의 training 시간 복잡도? -> O(1) 

data를 다 기억하기만 하면 되기 때문에

Q. Nearest Neighbor의 testing 시간 복잡도? -> O(N)

training example과 testing example을 매번 비교해야 함

testing은 빨라야 하고 training에는 시간이 오래 걸려도 상관없기 때문에 안 좋음.

k-nearest neighbors에서 k의 값이 늘어날수록 outlier가 줄어든다. 

• 해결을 위해서 L1 대신 L2 distance를 이용하기도 함
• with right choice of distance metric, we can apply K-Nearest neighbor to any type of data

K-nearest neighbor에서의 hyperparameters

• k, distance의 종류, 등등등...

data를 training set, validation set, test set으로 나눠서 검증해야 한다.

(validation set이 새로운 데이터의 역할을 한다)

Cross-validation: 데이터의 크기가 작을 때 주로 활용, 데이터를 여러 가지로 분리한 후에 validation으로 사용하고 결과의 평균치를 계산한다 (딥러닝에서는 자주 사용되지 않음!)

Curse of dimentionality

Linear classifier

Parametric approach

어떤 이미지가 픽셀로 주어져 있다. (32x32x3개의 숫자로 이루어진 array)

이 이미지를 10개의 class 중 하나로 분류를 해야 한다.

이거를 긴 column vector로 stretch한다 → x

Score function

f(x,W) = Wx + b

W: parameter/weight (가중치) 행렬

x: 이미지의 픽셀들을 column 한 줄로 stretch한 것

b: bias vector (데이터를 보정해주는 역할)

template matching approach→ 이 행렬에 있는 각각의 열이 이미지의 어떤 템플릿에 대응된다.

linear classifier의 한계: 하나의 template만 배우기 때문에, 만약 어떤 물체가 여러 가지 형태로 나타난다면 linear classifier로 training할 수가 없다.

Interpreting a linear classifier

하나의 이미지를 high-dimensional space에 있는 point로 생각할 수 있고, decision boundary가 n차원 면이 된다고 생각할 수 있다.

Hard cases for a linear classifier

decision boundary가 linear하지 않은 경우 원하는대로 잘 되지 않음. 

(kernel trick, feature engineering, neural networks with activation functions 등 다양한 방법이 있지만 아직 여기서는 다루지 않은 듯 하다 

아니 자꾸 자동저장 안 되고 날라가서 너무 빡침 그래서 대충만 다시 씀...