기술 블로그

[컴퓨터구조] 메모리 및 캐시 설계 가상 메모리

메모리Base CPI : 캐시 미스가 없을 때, 명령어를 실행하는 데 필요한 사이클 수Cycle Time : CPU의 클럭 주기 시간Miss Rate : 캐시에서 원하는 데이터를 찾지 못하는 비율Miss Penalty : 캐시 미스가 발생했을 때, 데이터를 가져오는 데 걸리는 시간입니다. 평균 메모리 접근 시간(AMAT) : 평균적으로 메모리에 접근하는 데 걸리는 시간AMAT = Hit Time + (Miss Rate * Miss Penalty) Hit Time = Base CPI * Cycle Time 만약 L1 캐시만 있다는 가정 하에서는Base CPI = 1Cycle Time = 0.5nsMiss Rate = 3%Miss Penalty = 100ns AMAT = (1*0.5) + (0.03 * 10..

[컴퓨터구조]페이지 폴트와 Use Bit의 이해

페이지 폴트 발생 시 use bit 페이티 폴트(Page Fault): CPU가 접근하려는 페이지가 현재 메인 메모리에 없을 때 발생하는 인터럽트페이지 교체 알고리즘 : 메인 메모리가 꽉 차서 새로운 페이지를 가져와야 할 때, 어떤 페이지를 내보낼지 결정하는 알고리즘Use bit : 각 페이지에 할당된 비트로, 페이지가 최근에 사용되었는지 여부를 나타냄Use bit 초기화 : 특정 시점에 모든 use bit을 0으로 설정하는 작업Use bit은 페이지가 사용되었는지 여부를 나타내는 지표이므로, 교체 시에는 최근에 사용되지 않은 페이지, 즉 use bit가 0인 페이지를 우선적으로 선택하여 교체합니다. Use bit의 초기화는 메모리 하드웨어 자체가 하는 것이 아니라 운영체제가 주기적으로 수행합니다. 운영..

[컴퓨터구조] 메모리 계층

캐시 : cpu와 주기적장치 사이에 위치한 고속의 작은 메모리로 자주 사용되는 데이터를 저장하여 메모리 접근 속도 향상L1캐시 : 캐시 계층 구조에서 CPU에 가장 가까운 캐시 CPI : 명령어 하나를 실행하는 데 필요한 클럭 사이클 수Miss Rate : 캐시에서 원하는 데이터를 찾지 못하는 비율메인 메모리 접근 시간 : 캐시 미스가 발생했을 때 메인 메모리에 접근하여 데이터를 가져오는 데 걸리는 시간평균 메모리 접근 시간 : 캐시 접근 시간과 메인 메모리 접근 시간을 고려한 평균적인 메모리 접근 시간 AMAT = Hit Time + (Miss Rate * Miss Penalty) Hit time : 캐시에서 데이터를 찾았을 때 걸리는 시간Miss Penalty : 캐시 미스가 발생했을 때 메인 메모리..

[컴퓨터구조] 포워딩 hazard 위험

데이터 해저드 포워딩 해결법포워딩 : 이전 명령어의 결과를 WB 단계까지 기다리지 않고, 필요한 단계에서 바로 다음 명령어에 전달하여 데이터 해저드를 해결하는 기술스톨(stall/bubble) : 필요한 데이터가 준비될 때까지 파이프라인의 진행을 일시적으로 멈추는 것 R-type 명령어의 연산 결과는 EX 단계에서 계산됩니다.  Load 명령어는 메모리 접근을 통해 데이터를 가져와야 하므로, 레지스터에 쓸 데이터는 MEM 단계에서 준비됩니다. R-type 명령어가 데이터를 사용하는 시점은 ID 단계에서 피연산자 레지스터의 값을 읽어 EX단계에서 수행합니다. Load 단계에서 주소 계산을 위해 ID 단계에서 레지스터 값을 읽고 EX에서 데이터를 사용합니다.  Beq 명령어는 분기 판단이 ex단계에서 이루어..

[컴퓨터구조] 파이프라인 해저드 (Pipeline Hazards) 및 해결 방법

Hazard 종류구조적 해저드 (Structural Hazards)필요한 하드웨어 자원을 여러 명령어가 동시에 사용하려고 할 때 발생합니다. 즉  하드웨어 자원 부족으로 인해 발생하는 충돌입니다. 예 ) 하나의 메모리 포트를 가진 시스템에서 명령어 인출과 데이터 접근이 동시에 일어나려고 할 때 발생합니다. 해결방법 : 하드웨어 추가, 파이프라인 정지 (stall) (버블삽입) 데이터 해저드 (Data Hazards)어떤 명령어가 이전에 실행된 명령어의 결과에 의존하는 경우, 이전 명령어가 결과를 생성하기 전에 다음 명령어가 그 결과를 사용하려고 할 때 발생합니다. 데이터 의존성으로 인해 발생하는 문제입니다. RAW(Read After Write) : 어떤 명령어가 이전에 실행된 명령어가 쓴 데이터를 읽으..

[컴퓨터구조] 파이프라인 및 제어신호

정리 표:명령어 유형명령어 예시WB 단계 수행 여부비고R-typeadd, sub, and, or, xor, nor, sll, srl, sra수행jr은 미수행I-typelw, lui수행데이터 전송 명령어I-typeaddi, andi, ori, xori, sw, beq, bne미수행연산 및 분기 명령어J-typej, jal미수행점프 명령어 5단계의 파이프라인 단계에서 IF - ID - EX - MEM - WB에서  load 명령어IF : 명령어 인출ID : 명령어 해독 및 주소 계산EX : 주소 계산MEM : 메모리에서 데이터 읽기WB : 메모리에서 읽은 데이터를 레지스터에 쓰기즉 load 명령어에서는 wb 단계를 수행합니다. store 명령어IF : 명령어 인출ID : 명령어 해독 및 주소 계산EX : 주..

[컴퓨터구조]

Single-cycle 프로세서Single-cycle 프로세서는 하나의 명령어가 각 단계를 하나씩 순차적으로 거쳐야 하므로, 한 명령어를 처리하는 데 필요한 시간은 모든 단계의 시간을 합친 것입니다. 즉 각 단계에서 걸리는 시간 중 가장 큰 값을 기준으로 클럭 주기를 설정해야 합니다.  예시)IF = 200psID = 150psEX = 250psMEM = 250psWB = 100ps 가장 오래 걸리는 시간은 EX와 MEM 단계로 250ps입니다. 하지만 single-cycle 프로세서에서는 모든 단계를 하나씩 순차적으로 처리하기 때문에, 모든 단계의 시간을 합쳐야 합니다. 따라서 최선의 클럭 주기는 모든 단계의 소모 시간의 합입니다. si200 + 150 + 250 + 250 + 100 = 950ps  ..

[컴퓨터구조] Processor1

MIPS 단계별 주요 자원IF (Instruction Fatch) 단계사용 자원 : Instruction Memory설명 : IF 단계에서는 명령어를 메모리에서 읽어오는 작업이 이루어집니다. 프로그램 카운터(PC) 기준으로 Instruction Memory에서 명령어를 가져옵니다.ID (Instruction Decode) 단계사용자원 : Register file설명 : ID단계에서는 명령어의 옵코드와 레지스터 주소를 해석하고, 명령어에서 요구하는 레지스터 값을 Register File에서 읽습니다. 예를들면 add $t0, $t1, $t2 명령어에서 $t1, $t2 값을 Register File에서 가져옵니다. EX (Execute) 단계사용 자원 : ALU설명 : EX 단계에서는 산술/논리 연산을 수행..

[컴퓨터구조] processor1

Load 명령어 실행 과정 레지스터 파일은 프로세서에서 레지스터를 저장하는 저장소입니다. 각 명령어를 실행할 때  CPU는 레지스터 파일에 접근하여 데이터를 읽거나 씁니다. Load 명령어는 메모리에서 데이터를 읽어와 레지스터에 저장하는 작업을 수행합니다. 이 과정에서 Register File에 두 번 접근하게 됩니다.  1. 첫 번째 접근load 명령어는 메모리 주소값이 저장된 레지스터를 읽어야 합니다.Register File에서 해당 레지스터를 읽는 것이 첫 번째 접근입니다.2. 두 번째 접근메모리에서 읽어온 데이터를 Register RFile의 특정 레지스터에 저장해야 합니다.이 과정에서 Register File에 다시 접근하여 데이터를 씁니다.다른 유닛들은 1번 접근하는 반면 Register Fi..

1번 문제 변형 문제 1. 다양한 퍼짐 속도를 가진 풀#include #include #include #include using namespace std;const int dx[] = {-1, 1, 0, 0};const int dy[] = {0, 0, -1, 1};int n, k;vector> grid, speed;int bfs(int startX, int startY) { vector> visited(n, vector(n, 0)); queue> q; vector> year(n, vector(n, 0)); int count = 1; q.push({startX, startY}); visited[startX][startY] = 1; year[startX][startY] ..