728x90

[문제]

링크: https://programmers.co.kr/learn/courses/30/lessons/42576

 

코딩테스트 연습 - 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수

programmers.co.kr

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

[제한사항]

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

[풀이]

위 문제 의도는 HashMap을 사용하여 문제를 해결하는 문제이다. 

그러나 배열만으로도 간단히 해결할 수 있기 때문에 두 가지 방법으로 풀어보았다.

1) 배열

public static String solution(String[] participant, String[] completion) {
    Arrays.sort(participant);
    Arrays.sort(completion);

    for (int i=0; i<completion.length; i++) {
        if (participant[i].equals(completion[i])) {
            continue;
        } else {
            return participant[i];
        }
    }

    return participant[participant.length-1];
}

각각 정렬을 하고 앞에서 부터 하나씩 비교를 한다.

동일하지 않으면 완주하지 못한 선수 이므로 출력해준다.

완주자 목록에 다른게 없다면 마지막 한 사람이므로 그 사람을 출력해준다.

2) HashMap

public static String solution(String[] participant, String[] completion) {
    String answer = "";

    Map<String, Integer> hm = new HashMap<>();
	
    for (String p : participant) {
        hm.put(p, hm.getOrDefault(p, 0)+1);
    }

    for (String c : completion) {
        hm.put(c, hm.get(c) - 1);
    }

    for (String key : hm.keySet()) {
        if (hm.get(key) != 0) {
            answer = key;
            break;
        }
    }

    return answer;
}

먼저 참여자를 Map에 하나씩 넣고 1씩 증가시켜준다. (동명이인이 있으면 2, 3... 이렇게 숫자가 추가된다.)

완주자 목록을 하나씩 읽으며 저장된 맵의 value를 1씩 감소시킨다.

마지막으로 for문을 돌며 Map에 저장된 value 값이 0이 아닌 사람의 이름을 출력해 준다.

[결과]

1) 배열

2) HashMap

728x90
728x90

병렬 분산 알고리즘 구현이 가능한 맵리듀스 프레임워크에 대해서 이야기하기 전에
왜❓ 병렬 분산 알고리즘을 사용해야 하는지 먼저 이야기 하겠습니다.


💡 병렬 분산 알고리즘을 사용하는 이유

  • Scale-out: 많은 수의 값싼 서버 이용
  • Scale-up: 적은 수의 값비싼 서버 이용

데이터 중심(data-intensive) 어플리케이션 분야에서는 Scale-out을 선호합니다.
왜냐하면 가격과 성능의 관계가 선형적으로 증가하지 않기 때문입니다.
예를 들면, 두배 성능의 프로세서 하나를 가진 컴퓨터의 가격이 일반적인 컴퓨터 가격의 두배보다 훨씬 비쌉니다.
그래서 수 십에서 수 천대의 컴퓨터를 묶어서 처리하기 위해 병렬 분산 알고리즘이 필요합니다.
그럼 병렬 분산 알고리즘 구현이 가능한 맵리듀스 프레임워크에 대해 이야기 하겠습니다.


🤔 Why MapReduce...?

데이터 중심 프로세싱(Data-intensive processing)에서는 한대의 컴퓨터로 처리하는데는 한계가 있습니다.
여러 컴퓨터를 묶어서 처리를 해야하는데 그 역할을 하는 것이 바로 맵리듀스(MapReduce)입니다

맵리듀스는 빅데이터를 활용하여 효율적인 계산이 가능한 첫 번째 프로그래밍 모델입니다.
Scalable(사용자 수, 데이터가 급증해도 프로그램 성능이 크게 떨어지는 일이 없는) 병렬 소프트웨어의 구현을 쉽게 할 수있도록 도와주는 프로그래밍 모델입니다.


✔️ MapReduce Programming Model

구글에서 맵리듀스 프레임워크를 만들었고 외부에서 사용할 때는 오픈소스인 하둡(Hadoop)을 이용하여 맵리듀스 프레임워크를 구현하여 사용합니다.

함수형 프로그래밍(Functional programming) 언어의 형태로 사용자는 3가지 함수(main, map, reduce) 를 구현해서 제공해야 합니다.

  • main 함수: 드라이브에 해당
  • map 함수: (key1, val1) -> [(key2, val2)]
    • org.apache.hadoop.mapreduce 패키지에 있는 Mapper 클래스를 상속받아 수행합니다.
  • reduce 함수: (key2, [val2] -> [(key3, val3)]
    • org.apache.hadoop.mapreduce 패키지에 있는 Reducer 클래스를 상속받아 수행합니다.

드라이브에 해당하는 main 함수는 map 함수와 reduce 함수를 차례대로 호출합니다.
map 함수와 reduce 함수 key와 value가 쌍으로 구성된 형태로 입력을 받고 출력을 합니다.
[]로 표시된 것은 list로 여러개 받을 수 있다는 것을 의미합니다.
Reduce 함수의 [val2]은 list 형태이고, map 함수와 reduce 함수의 출력은 하나도 없을 수도 있고 1개일 수도 있고 여러개 일 수도 있습니다.

이 세가지 함수에 추가로 combine 함수가 있습니다.

  • Combine 함수: reduce 함수와 유사
    • 각 머신에서 map phase에서 map 함수의 출력 크기를 줄여서 shuffling phase와 reduce phase의 비용을 줄여주는데 사용됩니다.

한번의 맵리듀스 페이즈는 map 함수를 먼저 호출하고 그 다음 reduce 함수가 호출됩니다.
필요하면 맵 함수가 끝난 후, combine 함수를 중간에 수행 할 수도 있습니다.

그럼 이 맵리듀스 프레임워크가 어떻게 동작하는지 더 자세하게 한번 알아보도록 하겠습니다.


🔍 MapReduce Framework

맵리듀스 프레임워크는 앞서 설명한데로 각각의 레코드(또는 튜플)이 (key, value)쌍으로 표현됩니다.
main 함수는 한개의 마스터 머신(master machine)에서 수행됩니다.
마스터 머신map 함수 수행 전 전처리를 하거나 reduce함수 결과를 후처리 하는데 사용될 수 있습니다.

맵리듀스는 3 단계로 아래 그림과 같이
map phase => shuffling phase => reduce phase 순서로 호출되어 수행됩니다.

Map Phase 3단계

MapReduce Phase

  • Map phase
    • 제일 먼저 수행되며 여러 파티션에 병렬 분산으로 호출되어 수행됩니다.
    • 그러면 각 머신에서 수행되는 mapper를 통해 입력 데이터 한 줄씩 map 함수가 호출됩니다.
    • map 함수는 (key, value)쌍 형태로 여러 머신에 나누어 보내지고 같은 key를 갖으면 같은 머신으로 보내집니다.
  • Shuffling phase
    • 모든 머신에서 map phase가 다 끝나면 시작됩니다.
    • map phase에서 각각의 머신으로 보내진 (key, value)쌍이 key를 기준으로 정렬됩니다.
    • 같은 key를 가진 (key, value)쌍을 모아서 value-list를 만듭니다. 그후 (key, value-list)쌍을 key에 따라 여러 머신에 분산해서 보냅니다.
  • Reduce phase
    • 모든 머신에서 shuffling phase가 다 끝나면 시작됩니다.
    • 각각의 머신에서는 shuffling phase에서 보낸 (key, value-list)쌍 마다 reduce 함수가 호출됩니다.
    • 하나의 reduce 함수가 끝나면 다음 (key, value-list)쌍에 호출됩니다.
    • (key, value)쌍 형태로 출력할 수 있습니다.

🐘 Hadoop

하둡은 Apache 프로젝트에서 만든 MapReduce 프레임워크 오픈 소스입니다.
여기에는 하둡 분산 파일 시스템(Hadoop Distributed File System - HDFS) 이라는 게 있습니다.

빅데이터 파일을 여러대의 컴퓨터에 나누어 저장을 합니다. 이 각 파일은 여러 개의 순차적인 블록으로 저장이 됩니다.
그리고 그 하나의 파일의 각각의 블록폴트 톨러런스(fault tolerance)를 위해서 여러개로 복사되어 여러 머신에 저장됩니다.

폴트 톨러런스는 시스템을 구성하는 부품의 일부에서 결함 또는 고장이 발생하여도 정상적으로 혹은 부분적으로 기능을 수행할 수 있게 하는 것을 말합니다. 그래서 하나의 파일 조각에 문제가 생겨도 다른 머신에 저장된 조각을 가져다 사용 할 수 있습니다.

🛠 구성 요소로 소프트웨어의 수행을 분산하기 위한 MapReduce 와 데이터 분산을 위한 HDFS 이 있습니다.
🛠 한 개의 Namenode(master)와 여러대의 Datanode(slaves)로 이루어져 있습니다.


🧐 이 글은 공부한 내용을 정리하고 공유하기 위해 작성한 글입니다!
🛠 수정해야 하는 내용이 있다면 알려주세요! 감사합니다 🙇‍♀️
728x90

'Hadoop > 이론' 카테고리의 다른 글

Matrix Addition  (0) 2021.09.16
Inverted Index  (0) 2021.09.15
Partitioner Class  (0) 2021.09.15
728x90

[문제]

https://programmers.co.kr/learn/courses/30/lessons/42578?language=java#

 

코딩테스트 연습 - 위장

 

programmers.co.kr

 

[문제 풀이]

- 얼굴: 동그란 안경, 검정 선글라스, none => 3가지의 경우의 수

- 상의: 파란색 티셔츠, none  => 2가지의 경우의 수

- 하의: 청바지, none => 2가지의 경우의 수

- 겉옷: 긴코트, none => 2가지의 경우의 수

 

총 3 * 2 * 2* 2 = 24가지가 나올 수 있다.

그런데 최소 한개의 옷을 입여야 하기 때문에 [none, none, none, none]을 고른 경우의 수 1개를 빼주어야 한다.

따라서 23가지

 

[코드]

public static int solution(String[][] clothes) {
  Map<String, Integer> hm = new HashMap<>();
  for (int i=0; i<clothes.length; i++) {
  	hm.put(clothes[i][1], hm.getOrDefault(clothes[i][1], 1) + 1);
  }
    
  int ans = 1;
  for (Integer value : hm.values()) {
  	ans *= value;
  }
  
  return ans-1;
}
728x90
728x90

💡 패리티비트 & 해밍코드 💡

데이터 오류 검출 방식

🔍 패리티비트 (Parity Bit)?

시리얼 통신에서 데이터의 오류를 검출하기 위한 일종의 장치 중 하나  
정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트로   
전송하고자 하는 데이터의 각 문자에 1비트를 더하여 전송한다.

짝수 패리티
데이터의 모든 1의 개수를 짝수로 맞춰야 한다.
예를 들어, 1100100 의 1의 개수는 3개(홀수) 이므로, 자동적으로 패리티 비트는 1이 되어(11100100) 총 1의 개수는 4개(짝수) 가 된다.

홀수 패리티
데이터의 모든 1의 개수를 홀수로 맞춰야 한다.
예를 들어, 1100100 의 1의 개수는 3개(홀수) 이므로, 패리티 비트는 0이 된다.

짝수 패리티일 때,
데이터가 중간에 손실되서 11100100 이 아닌 11000100 이 가게 된다면 데이터가 손실 되었다는 것을 알 수 있다.

🔍 패리티비트 특징

  • 2bit의 데이터가 손실되면 알아차릴 수 없다.
  • 오류 검출만 할 뿐 수정하지는 않는다.

🔍 해밍 코드 (Hamming code)

데이터 전송 시, 1비트의 에러를 정정할 수 있는 자기 오류정정 코드   
패리티비트를 보고, 1비트에 대한 오류를 정정할 곳을 찾아 수정할 수 있다.

해밍 코드 생성 규칙

2의 n승 번째 자리인 1,2,4번째 자릿수가 패리티 비트.
이 숫자로부터 시작하는 세개의 패리티 비트가 짝수인지, 홀수인지 기준으로 판별한다.

짝수 패리티의 해밍 코드가 0011011일때, 오류 수정

1, 3, 5, 7번째 비트 확인 : 0101로 짝수이므로 '0'
2, 3, 6, 7번째 비트 확인 : 0111로 홀수이므로 '1'
4, 5, 6, 7번째 비트 확인 : 1011로 홀수이므로 '1'

역순으로 패리티비트 '110'을 10진법으로 바꾸면 '6'이므로 6번째 비트를 수정하면 된다.
따라서 수정한 데이터는 0011001이다.

728x90

'Computer Science > Computer Architecture' 카테고리의 다른 글

6. 파이프라이닝  (0) 2023.06.27
4. 고정소수점 & 부동소수점  (0) 2021.08.02
3. Cache Memory  (0) 2021.07.20
2. CPU  (0) 2021.07.18
1. Structure  (0) 2021.07.14
728x90

💡 고정 소수점 & 부동 소수점 💡

고정 소수점과 부동 소수점은 소수점이 포함된 실수를 표현하는 방식.

🔍 고정 소수점(Fixed Point)?

소수점이 고정된 형태   
소수점이 찍힐 위치를 미리 정해놓고 소수를 표현하는 방식   

부호, 정수, 소수로 3요소로 나눠서 표현한다.

🔍 고정 소수점 특징

  • 장점
    실수를 정수부와 소수부로 표현하여 비교적 단순하다.
  • 단점
    표현의 범위가 너무 적어서 활용하기 힘들다.
    정수부는 15bit, 소수부는 16bit

이러한 한계를 해결해주는 것이 부동 소수점이다.

🔍 부동 소수점?

지수의 값에 따라 소수점이 움직이는 방식을 활용한 실수 표현 방법이다.

가수부와 지수부로 표현한다.
가수: 실수의 실제값 표현
지수: 크기를 표현, 가수의 어디쯤에 소수점이 있는지를 나타냄.

🔍 부동 소수점 특징

  • 장점
    고정 소수점 방식보다 훨씬 더 많은 범위까지 표현할 수 있다.
  • 단점
  • 오차가 존재한다
728x90

'Computer Science > Computer Architecture' 카테고리의 다른 글

6. 파이프라이닝  (0) 2023.06.27
5. 패리티비트 & 해밍코드  (0) 2021.08.02
3. Cache Memory  (0) 2021.07.20
2. CPU  (0) 2021.07.18
1. Structure  (0) 2021.07.14
728x90

[문제]

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

[문제 풀이]

이 문제는 BFS 또는 DFS를 이용하여 해결 할 수 있다.

그리고 BFS와 DFS를 구현하는데 matrix 또는 list로 구현이 가능한데 두 가지 방법으로 다 풀어보았다.

 

1. BFS Linked list

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;
    static Node[] adj;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());
        M = stoi(br.readLine());

        visited = new boolean[N+1];
        adj = new Node[N+1];

        for (int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

        System.out.println(bfs(1));
    }

    public static int bfs(int n) {
        int cnt = 0;
        visited[n] = true;
        q.offer(n);

        while(!q.isEmpty()) {
            int x = q.poll();

            for (Node node=adj[x]; node!=null; node=node.next) {
                if (!visited[node.n]) {
                    q.offer(node.n);
                    visited[node.n] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

2. DFS Linked list

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static Node[] adj;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public  static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        adj = new Node[n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (Node node=adj[v]; node!=null; node=node.next) {
            if (!visit[node.n]) {
                cnt++;
                dfs(node.n);
            }
        }
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

3. DFS Matrix

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[][] matrix;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public  static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        matrix = new int[n+1][n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            matrix[u][v] = 1;
            matrix[v][u] = 1;
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (int i=1; i<=n; i++) {
            if (matrix[v][i]==1 && !visit[i]) {
                cnt++;
                dfs(i);
            }
        }
    }
}

[결과]

BFS - list

DFS - list

DFS - matrix

순으로 결과는 다음과 같이 나왔다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1991 트리 순회 - Java  (0) 2021.07.16
[BOJ] 5639 이진 검색 트리 - Java  (0) 2021.07.16
[BOJ] 1068 트리 - Java  (0) 2021.07.14
[BOJ] 11279 최대 힙 - Java  (0) 2021.07.14
[BOJ] 1927 최소 힙 - Java  (0) 2021.07.14
728x90

💡 캐시 메모리 💡

🔍 Cache Memory?

메인 메모리와 CPU간의 데이터 속도 향상을 위한 중간 버퍼 역할을하는 메모리
캐시는 블록(Block)으로 구성. 각각의 블록은 데이터를 담고 있다.

🔍 Cache 특징

  • 장점
  • 주소값을 키로써 접근하기 때문에 메모리 계층 구조에서 가장 빠른 소자. 처리속도가 거의 CPU의 속도와 비슷할 정도의 속도
  • 주 기억 장치를 접근하는 횟수가 줄어들어 컴퓨터의 처리속도가 향상
  • 단점
  • 용량이 적음
  • 상대적으로 가격이 비쌈
  • 지워질 수 있으며 영구적인 메모리가 아니다.
따라서 캐시는 빈도수가 높은 것들 위주로 데이터량이 많지 않은 것이 좋다.

🔍 Cache 종류

Cache memory에는 L1, L2, L3가 있다.   
L은 level의 약자로 L1 -> L2 -> L3 -> 순으로 데이터를 찾는다.

1. L1
CPU 내부에 존재. 프로세서와 가장가까운 캐시
2. L2
CPU와 RAM 사이에 존재. 용량이 큰 캐시
3. L3
보통 메인보드에 존재. 멀티 코어 시스템에서 여러 코어가 공유하는 캐시.

🔍 작동 원리

CPU가 메모리에 접근하기 전 먼저 캐시 메모리에서 원하는 데이터의 존재 여부 확인
이때 필요한 데이터가 있는 경우 hit, 없는 경우를 miss

  • 공간적 지역성: 한 번 참조한 메모리의 옆에 있는 메모리를 다시 참조하게 되는 성질
  • 시간적 지역성: 한 번 참조된 주소의 내용은 곧 다음에 다시 참조된다는 특성

🔍 캐시 미스

1. Compulsory miss (= cold miss) 강제 미스
데이터에 접근시 캐시에 메모리를 올리기 위해 발생하는 캐시 미스.

2. Conflict miss
Cache에서 set의 way가 부족하여 발생하는 miss.
Direct map이나 Set associative 방식에서 같은 부분을 번갈아 가면서 사용하게 되어 발생하는 miss.

3. Capacity miss
캐시의 용량이 부족하여 발생하는 miss.
프로그램 수행 시 접근하는 데이터의 양이 캐시의 사이즈를 넘어갈 경우 miss.

728x90

'Computer Science > Computer Architecture' 카테고리의 다른 글

6. 파이프라이닝  (0) 2023.06.27
5. 패리티비트 & 해밍코드  (0) 2021.08.02
4. 고정소수점 & 부동소수점  (0) 2021.08.02
2. CPU  (0) 2021.07.18
1. Structure  (0) 2021.07.14
728x90

💡 CPU 작동 원리 💡

🔍 CPU?

CPU는 컴퓨터에서 가장 핵심적인 역할을 수행하는 부분.
'인간의 두뇌'
연산장치, 제어장치, 레지스터 3가지로 구성됨

🔍 CPU의 구성

  • 연산장치: 산술 연산과 논리 연산을 수행
    연산에 필요한 데이터를 레지스터에서 가져오고, 연산 결과를 다시 레지스터로 보내 저장.
  • 제어장치: 명령어를 순서대로 실행할 수 있도록 제어
    주기억장치에서 프로그램 명령어를 꺼내 해독
    그 결과에 따라 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력장치로 보냄.
    보낸 신호를 받아 다음에 수행할 동작 결정.
  • 레지스터: 고속기억장치로 명령어 주소, 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장
    • 범용 레지스터: 연산에 필요한 데이터나 연산 결과를 임시로 저장하는 레지스터
    • 특수 레지스터: 특별한 용도로 사용하는 레지스터. 용도와 기능에 따라 구분
    • - MAR (메모리 주소 레지스터): 읽기와 쓰기 연산을 수행할 주기억장치 주소 저장 - PC (프로그램 카운터): 다음에 수행할 명령어 주소 저장 - IR (명령어 레지스터): 현재 실행 중인 명령어 저장 - MBR(메모리 버퍼 레지스터): 주기억장치에서 읽어온 데이터 or 저장할 데이터 임시 저장 - AC (누산기): 연산 결과 임시 저장

🔍 CPU 동작

  1. 주기억장치는 입력장치에서 입력받은 데이터 또는 보조기억장치에 저장된 프로그램을 읽어온다.
  2. 중앙처리장치는 프로그램을 실행하기 위해 주기억장치에 저장된 프로그램 명령어데이터를 읽어와 처리하고
    결과를 다시 주기억장치에 저장
  3. 주기억장치는 처리 결과를 보조기억장치에 저장하거나 출력장치로 보냄
  4. 제어장치는 1~3에서 명령어가 순서대로 실행되도록 각 장치 제어

인출 사이클의 마이크로연산

T0: MAR <- PC
T1: MBR <- M[MAR], PC <- PC + 1
T2: IR <- MBR

PC에 지정된 주소를 MAR로 전달.
MAR에 저장된 내용을 토대로 주기억장치의 해당 주소에서 명령어 인출
인출한 명령어를 MBR에 저장

다음 명령어 인출을 위해 PC(프로그램카운터) 값 증가

MBR(메모리 버퍼 레지스터)에 저장된 내용을 IR(명령어 레지스터)에 전달.

ADD Addr명령어 연산

T0: MAR <- IR(Addr)
T1: MBR <- M[MAR]
T2: AC <- AC + MBR

메모리에 저장된 데이터 값을 MBR에 저장
IR에 MBR의 값이 이미 저장된 상태이기 때문에 PC <- PC + 1 명령어는 필요하지 않음.
AC에 MBR을 더한 값 저장.

🔍 용어정리

중앙처리장치 CPU
인간으로 따지면 두뇌에 해당하는 부분
주기억장치에서 프로그램 명령어와 데이터를 읽어와 처리하고 명령어의 수행 순서를 제어함

  • 중앙처리장치는 비교와 연산을 담당하는 산술논리연산장치(ALU)
  • 명령어의 해석과 실행을 담당하는 제어장치,
  • 속도가 빠른 데이터 기억장소인 레지스터로 구성
    개인용 컴퓨터와 같은 소형 컴퓨터에서는 CPU를 마이크로프로세서라고 부름

연산장치
산술 연산과 논리 연산을 수행
연산에 필요한 데이터를 레지스터에서 가져오고, 연산 결과를 다시 레지스터로 보내 저장.

제어장치
명령어를 순서대로 실행할 수 있도록 제어
주기억장치에서 프로그램 명령어를 꺼내 해독
그 결과에 따라 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력장치로 보냄.
보낸 신호를 받아 다음에 수행할 동작 결정.

레지스터
고속기억장치로 명령어 주소, 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장

범용 레지스터
연산에 필요한 데이터나 연산 결과를 임시로 저장하는 레지스터
특수 레지스터
특별한 용도로 사용하는 레지스터. 용도와 기능에 따라 구분

MAR (메모리 주소 레지스터)
읽기와 쓰기 연산을 수행할 주기억장치 주소 저장
PC (프로그램 카운터)
다음에 수행할 명령어 주소 저장
IR (명령어 레지스터)
현재 실행 중인 명령어 저장
MBR(메모리 버퍼 레지스터)
주기억장치에서 읽어온 데이터 or 저장할 데이터 임시 저장
AC (누산기)
연산 결과 임시 저장

728x90

'Computer Science > Computer Architecture' 카테고리의 다른 글

6. 파이프라이닝  (0) 2023.06.27
5. 패리티비트 & 해밍코드  (0) 2021.08.02
4. 고정소수점 & 부동소수점  (0) 2021.08.02
3. Cache Memory  (0) 2021.07.20
1. Structure  (0) 2021.07.14

+ Recent posts