728x90 반응형 분류 전체보기322 [Algorithm] 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘 (Kruskal algorithm) 다음과 같은 그래프가 있다고 해보자. 신장 트리는 그래프의 부분적인 트리라고 볼 수 있는데 그래프의 모든 노드를 갖고 있지만 에지의 경우 사이클이 생기지 않는 최소 부분만 가지고 있는 트리이다. 위의 그래프의 신장 트리는 여러 경우의 수가 존재한다. 많기 때문에 일부만 소개한다. 최소 신장 트리란 가중 그래프의 신장 트리 중에서 가장 가중치의 합이 작은 트리를 의미한다. 이렇나 최소 신장 트리를 구하는 방법인 Prim's algorithm과 Kruskal's algorithm에 대해서 공부해보려 한다. Prim algorithm 노드 하나를 선택한다. 선택된 노드들과 이어진 노드들 중 가장 가중치가 적은 노드를 고른다. 지금까지 선택된 노드들과 연결된 노드들 중 가장 가중치가 적은 노드를 고른다. 위 방.. 2022. 12. 17. [컴퓨터구조론] 캐시 메모리 블록 사상 방식 메모리 계층 구조는 위 그림과 같다. 아래에서 위로 갈수록 가격이 비싸고 속도가 빠르며 용량이 적다. 계층 구조 중 캐시 메모리에 대해서 공부해보려한다. 캐시 메모리 캐시 메모리는 CPU와 메인 메모리 사이의 속도 차이를 줄이기 위해 필요하다. CPU는 원하는 데이터를 가져오기 위해서 아래와 같은 과정을 거친다. CPU가 캐시 메모리에 워드를 요청한다. 존재하면 가져오고 존재하지 않으면 2번으로 간다. CPU가 메인 메모리에 워드를 포함한 블록을 요청한다. 존재하면 블록을 복사하여 캐시 메모리에 보내고 3번으로 간다. 존재하지 않으면 4번으로 간다. 캐시 메모리에 복사된 블록이 존재하므로 다시 캐시 메모리에 워드를 요청하여 가져온다. CPU가 보조 저장장치에 페이지를 요청하여 메인 메모리로 가져온다. C.. 2022. 12. 16. [컴퓨터구조론] 파이프라이닝과 해저드 이전 포스팅에서 데이터 경로에 대해서 공부했었다. https://growth-coder.tistory.com/37 두 가지 방식 중 다중 사이클 방식을 사용하면 오늘 공부할 파이프라이닝을 구현할 수 있다. 파이프라이닝 다중 사이클 방식은 하나의 명령어가 여러 개의 사이클을 사용하기 때문에 하드웨어 장치에 여러 번 접근할 수 있다. 어떤 명령어가 A, B, C, D의 사이클로 이루어져 있다고 해보자. 이러한 명령어를 여러 번 수행한다고 하면 위와 같이 하나의 명령어가 끝나고 다음 명령어를 실행하는 방식으로 수행이 될 것이다. 그러나 다중 사이클 방식을 사용한다면 하나의 사이클이 끝나고 다음 사이클에서는 이전 사이클에서 사용된 하드웨어에 접근할 수 있기 때문에 아래와 같은 파이프라이닝이 가능하다. 하나의 사.. 2022. 12. 15. [컴퓨터구조론] 데이터 경로 (단일 사이클 방식, 다중 사이클 방식) CPU는 명령어를 실행시키기 위해 데이터를 하드웨어 장치로 보내야한다. 이렇게 데이터가 여러 하드웨어 장치로 이동하는 경로를 데이터 경로라고 한다. 지금까지 MIPS 명령어 사용법을 공부했는데 이제 16비트 picoMIPS 명령어 집합을 기준으로 데이터 경로를 공부해보려 한다. 데이터 경로는 크게 단일 사이클 방식과 다중 사이클 방식으로 나뉜다. 단일 사이클 방식 초기에는 단일 사이클 방식이 사용되었는데 이는 하나의 명령어가 하나의 사이클 내에서 수행되는 방식이다. 이러한 방식은 하나의 명령어가 한 사이클 동안 전체 데이터 경로를 사용하므로 하나의 명령어가 실행되는 동안은 하드웨어 장치에 두 번 이상 접근할 수 없다. 이러한 이유 때문에 단일 사이클 방식은 PC 갱신 장치를 필요로 한다. 다음 명령어의 .. 2022. 12. 14. 이전 1 ··· 69 70 71 72 73 74 75 ··· 81 다음 728x90 반응형
