[2024.10.16] 컴퓨터 공학 개론

* 강의를 듣고 필기한 내용일 이후에 따로 정리한 내용입니다.

* https://glowdp.tistory.com/28 에서 이어지는 게시물 입니다.

---

Sorting algorithms

 

- 정렬 알고리즘은 주어진 데이터를 정해진 순서대로 재배열하는 알고리즘이다. (ascending, descending)

• Bubble Sort
  - Time Complexity : O(N^2)
  - 인접한 두 원소를 비교하면서 큰 값을 뒤로 보내며 정렬
  - 가장 큰 값을 가장 마지막으로 보내는 것 = 한번의 step
      - 한번의 step이 끝나면 뒤에서부터 정렬
  
  - 버블정렬의 시간복잡도는 O(N^2)이고 어느정도 정렬된 상황에서는 swap이 많이 일어나지 않아 효과적이라고 볼 수 있음.

# bubble sort를 구현해봅시다!
def bubble_sort(L): # L = [-2, 45, 0, 11, 9]
	pass

L = [-2, 45, 0, 11, 9]
print(bubble_sort(L))
print(sorted(L))  # 비교

• Selection Sort(선택정렬)
  - 최솟 값을 맨 앞으로 보낸다 : 할려고 하는 것은 bubble sort랑 동일함, 하지만 코드는 다름
  - 최솟값을 찾아 위치를 바꿈
  - 정렬을 진행하면서 앞에서부터 차례로 정렬
  - index 0는 1~n, index 1은 2~n까지를 반복하며 최솟값을 찾고 위치를 바꾸는 것을 반복
  - 시간 복잡도는 O(N^2)의 시간복잡도
  - 다른 O(N^2) 정렬 알고리즘과 비교해봤을 때도 성능이 떨어지는 편

def selection_sort(arr):
    min_value = 99999999
		for i in range(n):
				if arr[i] < min_value:   #arr[i]가 min_value보다 작으면
		arr[0] = min_value

• Insertion Sorting(삽입 정렬)
  - 리스트의 요소를 하나씩 가져와서 이미 정렬된 앞 부분과 비교하여 적절한 위치에 삽입
  - 시간복잡도는 O(N^2)이며 작은 값들이 뒤쪽에 몰려있으면 최악의 경우
  - 사이즈가 작을 경우 매우 효율적이라 고성능 정렬 알고리즘들도 사이즈가 작을 경우 삽입 정렬보다 오래 걸릴 수 있음

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

• (Advanced) Quick Sort(퀵 정렬)
  - 키워드 : divide and conquer, dynamic programming, greedy algorithm, backtracking
  - divide and conquer(분할 정복) 방식을 쓰는 알고리즘
  - 분할정복 : 복잡한 전체의 문제를 부분으로 나누어, 부분적인 문제를 해결하고 다시 합쳐 전체를 해결하는 방식을 의미
  - 코드의 시간 복잡도는 평균적으로 O(N logN)이지만, 최악의 경우 O(N^2)의 시간 복잡도를 가짐
  - (암기하기) 퀵소트의 평균적인 복잡도 : O(N logN) , 최악의 경우엔 O(N^2)
  - 피벗 값을 정하는 방식 등 세부 구현 방법이 중요함.

def quick_sort(arr):    # using recursion
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, equal, right = [], [], []
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num == pivot:
            equal.append(num)
        else:
            right.append(num)
    return quick_sort(left) + equal + quick_sort(right)

 

Searching algorithms

• Linear Search (순차 탐색, 전탐색)
      - 처음부터 끝까지 순서대로 모든 데이터를 탐색하는 방법. 요즘 거의 사용을 하지 않음
      - 리스트, 배열 등 선형 구조에서 데이터를 검색할 때 사용됨
      - for문을 이용해서 앞에서부터 원하는 값을 찾기 때문에, O(N) 의 시간복잡도를 가짐.
                → 만약에, search 자체를 몇 번 안한다면 Linear Search도 괜찮음!

def linear_search(arr, x):
    """
    arr : 리스트
    x : 찾고자 하는 값
		result : return value, 찾은 값의 index
    """
		pass

# 예시
arr = [1, 3, 5, 7, 9]
x = 7
result = linear_search(arr, x)
if result == -1:
    print("찾는 값이 리스트에 없습니다.")
else:
    print(f"{x}은(는) 리스트의 인덱스 {result}에 위치합니다.")

• Binary Search (이진 탐색) : 가능하면 쓰면 됨
  - 정렬된 데이터에서 특정 값을 찾을 때 사용하는 탐색 방법
  - 정렬된 데이터셋(이진 트리, 배열)에서 중간값을 찾아서 검색 대상을 반으로 줄여가며 탐색을 진행.
                  (search space가 줄어든다)
  - O(log2N)의 시간복잡도를 가지며 이미 정렬이 되어 있는 데이터셋에서는 큰 효율성을 가진다.
  - 단점 : 정렬이 되어있어야 한다, 정렬이 안 되어있으면 못 씀!!!! sorting을 해야함!!!!!!
  - 장점 : 무지하게 빠름 + 굉장히 좋은 방법
  
  → 랜덤하게 구성된 데이터를 binary search로 탐색할 때 : O(NlogN) + C X O(logN)
  → 랜덤하게 구성된 데이터를 linear search로 탐색할 때 : C XO(N)
  
  - Binary Search Tree
  
     -TreeNode 클래스는 이진 탐색 트리의 노드를 나타내며, BST 클래스는 이진 탐색 트리를 나타낸다. 
     - 바이너리 서치 트리의 설명 : https://www.geeksforgeeks.org/binary-search-tree-data-structure/

  

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class BST:
    def __init__(self):
        self.root = None

 

Insert
    - **Tree는 원래의 트리에 새로운 Node를 추가하는 식으로 구현. 
    → 특별한 규칙이 없다면, left child부터 채웁니다.**
    - Binary Search Tree이기 때문에 부모노드보다 크면 오른쪽, 작으면 왼쪽에 추가됨.

 

• Tree Search
  - Tree를 이용해 데이터를 탐색하는 방식
  - 데이터를 Tree로 표현한 뒤에 Tree에서 원하는 원소를 탐색하는 방식
  - Tree를 만드는데 추가로 시간이 들지만(O(N^2)), 그 이후에 탐색 시간이 O(log_2N)으로 줄어들게 되는 이득
  - 키워드 :  multi-dimensional data , GIS(Geospatial Information System) : 2, 3차원
                 LLM을 위한 Vector Index : 50, 300, 768, 1024, 2048차원
                 R-tree , B+-tree, R-tree, KD-tree, VP-tree, t-SNE, 
  
  
• Depth-First Search : depth를 먼저보고 탐색하는 방식.
  - tree level이 계속 증가하는 방향으로 탐색을 하다가, 더 이상 child node가 없을 때 다시 parent node로 올라와서 다른 child node들을 순차적으로 탐색
  
  
• Breadth First Search : DFS와 다르게 같은 level의 다른 child node들을 먼저 탐색하는 방식.
  - 같은 level의 모든 node를 탐색하면 가장 왼쪽 끝에 있는 다음 level의 노드부터 순차적으로 탐색함.
  
  
• 예시로 DFS 랑 BFS 찾기

* DFS 방식으로 찾으면 방문 순서 : 1→2 →4 (DFS에서는 돌아가지 않음) → 5 ( 3 - X, 더 위의 래벨로 가지 않음) → 6 → 7 → 8

    1) 지나온(방문한 노드) 노드는 다시 탐색하지 않는다.
    2) 여러개의 노드와 연결되어있다면 그 중에서 우선순위를 두고, 탐색을 수행
* BFS 방식으로 찾으면 방문 순서 1 → 2 → 3 (옆을 모두 보면서 내려감) → 4 →5→6→7→8

---

Computer Architecture

Computer Organization and Architecture

• computer architecture
  - 컴퓨터 시스템의 구조와 구성요소, 그리고 이들 간의 상호작용에 대한 설계와 구현을 다루는 분야
  - 컴퓨터 시스템의 성능, 신뢰성, 에너지 효율성 등을 결정하는데 중요한 역할
  - 프로세서와 메모리 간의 데이터 전송 방식, 명령어 집합 구성, 파이프라인 구조, 캐시 구조 등 다양한 요소들을 고려하여 설계- - 컴퓨터 시스템의 성능을 최적화하고, 에너지 효율성을 향상시키는 등 다양한 목적을 달성|
  - 컴퓨터 시스템의 구성요소들 간의 상호작용을 이해하고 최적화하는데 필수적인 지식
  
  
• components of a computer system
  - CPU (Central Processing Unit) : 프로그램의 명령어를 해석하고 실행하는 역할
                - 산술 논리 연산 장치(ALU), 제어 장치, 레지스터 등으로 구성
  - Main Memory (= Primary Memory) : 프로그램이나 데이터를 저장하는 공간
                - CPU가 작업을 수행할 때 필요한 명령어나 데이터가 저장
                - 주 메모리인 RAM (Random Access Memory). (Volatile)
  - Input Device : 사용자가 컴퓨터에 데이터나 명령을 입력하는 장치 (키보드, 마우스 등)
  - Output Device : 컴퓨터에서 처리한 결과를 사용자에게 보여주는 장치 (모니터, 스피커 등)
  - Storage (=Secondary Memory) : 데이터를 임시적, 반영구적으로 저장하는 장치
                        (하드 디스크 드라이브, SSD, USB 플래시 드라이브)
  - Bus : 컴퓨터 내부에서 데이터와 명령어를 전송하는 통로
                 - 버스는 데이터 버스, 주소 버스, 제어 버스 등
  - (Mother)Board : CPU, 메모리, 버스 등의 하드웨어 요소들이 담겨 있는 회로 기판
                 - 보드는 다양한 부품들이 부착되어 있어서 시스템의 기능과 성능을 결정
  
  

폰 노이만 아키텍쳐(Von Neumann Architecture)

• 컴퓨터의 기본적인 architecture 중 하나
• 프로그램과 데이터가 같은 메모리 공간에서 저장되어 처리되는 구조
• 대부분의 일반적인 컴퓨터 시스템은 Von Neumann architecture를 기반으로 설계
• CPU, 메모리, 입출력 장치로 구성
      - CPU는 메모리에서 명령어와 데이터를 읽어와 처리
      - 메모리는 프로그램 코드와 데이터를 저장
      - 입출력 장치는 컴퓨터와 외부 환경 간의 데이터 송수신을 담당
• 명령어와 데이터가 동일한 메모리에 저장되어 있음 : 명령어와 데이터를 구분하기 위한 별도의 제어 신호가 필요하지 않음
• CPU는 메모리에서 순차적으로 명령어를 읽어와 실행하는 방식으로 동작
  
  
• 단점 : 명령어와 데이터를 동시에 처리할 수 없음
       : CPU가 명령어를 실행하는 동안에는 데이터 처리함
             -> 병목 현상을 일으킬 수 있기 때문에, 현대 컴퓨터에서는 병렬 처리 기술 등을 이용해 이러한 한계를 극복

Instruction Cycle

• CPU가 메모리로부터 1개의 명령어를 가져와 어떤 동작을 요구하는지 결정하고 이를 수행하는 연속적인 과정
• 구분 단계
  1. Fetch
        - CPU가 Instruction을 memory로부터 1word를 읽어 다음으로 실행할 명령어를 인출
        - CPU는 메모리 주소 버스를 이용해 메모리 주소를 지정하고, 데이터 버스를 통해 명령어를 인출
                  (1 WORD = 현재 CPU가 처리하는 최소 정보처리 단위, 현재는 거의 다 64-Bits)
  2. Decode
        - CPU가 인출한 명령어를 해독하여 명령어가 어떤 작업을 수행해야 하는지를 결정
        - CPU는 명령어의 오퍼랜드(operand)와 연산자(operator)를 구분
        - 해당 명령어에 필요한 레지스터나 메모리 주소 등을 결정
  3. Execute
        -  CPU가 결정된 명령어를 실행 : CPU는 필요한 연산을 수행
  4. Memory (Access)
        -  CPU가 메모리에 접근하여 데이터를 읽거나 쓸 수 있음
        -  CPU는 메모리 주소를 결정하고, 데이터 버스를 통해 메모리와 데이터를 주고 받음
  5. Write Back
        -  계산된 결과를 레지스터(Register , cpu가 쓰는 메모리, 가장 빠르고 가장 비쌈.)에 저장
        -   CPU는 결과를 저장할 위치를 결정하고, 데이터 버스를 통해 결과를 저장
  
  

Central Processing Unit

Overview of the CPU

 

- 컴퓨터 시스템의 핵심 요소 중 하나로 프로그램의 명령어를 해석하고 실행하는 역할을 담당
- CPU는 모든 컴퓨터 시스템에서 필수적인 구성 요소이며, 컴퓨터의 속도와 성능에 큰 영향
- 작은 실리콘 칩에 위치하며, 코어(core라고 불리는 작은 계산 논리 회로의 집합으로 구성
     -  다양한 명령어를 수행하고, 데이터를 처리하고, 메모리와 입출력 장치와의 통신을 관리
- 여러 개의 코어(physical core)를 가진 멀티코어 프로세서가 일반적
     - 여러 가지 작업을 병렬로 처리하여 컴퓨터의 처리 속도를 향상시키는 데 도움을 줌
- 클럭 속도라고 불리는 주파수로 측정되는 작업 속도를 가지고 있음
     - 속도가 높을수록 CPU가 처리할 수 있는 명령어 수가 늘어나고, 컴퓨터의 처리 속도가 빨라짐

• Components of CPU
  - Control Unit(CU) : 제어 장치는 CPU에서 프로그램의 명령어를 해석하고, 실행 
      - 제어 장치는 명령어 레지스터에서 현재 실행 중인 명령어를 가져와서, 해당 명령어를 해석하고, 이에 맞게 다른 구성 요소들을 제어
  - ALU(Arithmentic / Logic Unit) : 산술 논리 장치는 CPU 내부에서 수치 연산과 논리 연산을 처리하는 부분
      - 산술 논리 장치는 두 개의 입력 신호를 받아서, 덧셈, 뺄셈, 곱셈, 나눗셈 등의 산술 연산을 처리하고, AND, OR, NOT 등의 논리 연산을 처리
  - Register :  CPU 내부에 저장되어 있는 소규모 메모리로, 데이터를 저장하거나 처리하는 데 사용
      - 가장 작고, 가장 빠르고, 비쌈
      -  CPU에서 가장 빠른 속도로 데이터를 처리할 수 있으므로, CPU의 속도와 성능에 큰 영향을 미침
  -> 현대 대부분 CPU는 CPU 내부에 Cashe memory에 위치

성능 향상을 위한 작업 방법

• Pipelining (단계별 병렬처리) → Sync(시간에 동기화되어있다)
     -여러가지 작업을 수행하는 데에 여러 단계의 작업이 필요한 경우, 이 단계들을 연속적으로 실행하여 시간을 단축시키는 기술
            - 한 번에 여러 단계를 처리하여 실행 시간을 단축시키는 것
  
  
• Parallellism (독립적인 병렬처리) → Async(시간에 동기화가 되어있지 않아도 된다)
     - 한 번에 여러 작업을 수행
     - 여러 개의 CPU 코어(코어가 하나면 안 됨)를 사용하여 병렬적으로 작업을 처리
     - 이러한 기술은 동시에 여러 작업을 수행하므로, 실행 시간을 단축시키는 것
  
  
• 둘의 차이점
  - Pipelining : 하나의 작업을 여러 단계로 분할하여 각 단계를 병렬적으로 처리하여 실행 시간을 단축시키는 것
  - Parallellism : 여러 작업을 동시에 처리하여 실행 시간을 단축시키는 것
  - > 두 기술은 함께 사용가능 (CPU에서는 파이프라인 기술을 사용하여 명령어를 처리하면서, 동시에 여러 개의 코어를 사용하여 병렬적으로 다른 작업을 수행)
  - Rendering, Raster processing, brightness, contrast, color adjustment, …
                                                  → **실수(float) 벡터 연산**
  - CUDA(Compute Unified Device Architecture) framework : NVIDIA가 만든 그래픽 처리용 언어 체계.
  - AlexNet(2012) → 딥러닝 모델을 학습시키려면, **실수 행렬 연산이 엄청 많이 필요**했음.
  
  - cuDNN framework : CUDA 기반 딥러닝 수치연산에 최적화된 라이브러리.
  - GPGPU(General Purpose GPU) : GPU가 실수 병렬연산에 최적화가 되어있는 것을 착안하여, 동시에 엄청나게 많은 실수 연산을 수행할 수 있게 최적화한 하드웨어.
  - tensorflow, pytorch, … → CUDA, cuDNN에 dependency
  - 그래서 딥러닝 업계에서는 NVIDIA 그래픽 카드가 legacy
  - GPGPU에는 독립적인 메모리(VRAM)가 있습니다.
               → 병렬처리를 하기 위해서는 VRAM에 데이터와 명령어가 올라와 있어야함

 

• Colab Pro ($9.9) -> T4, L4, A100 : 코딩공부할때 추천
• Colab Pro+ ($49.99) -> T4, L4, A100

Memory Organization and Management

Memory Hierarchy

Memory hierarchy는 컴퓨터에서 데이터와 명령어를 저장하는 계층 구조

Memory hierarchy는 컴퓨터에서 데이터와 명령어를 저장하는 계층 구조를 말한다. 
- speed(performance) : Register > L1 Cache > L2 Cache > L3 Cache > Main(DRAM) 
                                               >>> Secondary(SSD)   >>>>>>>>>> Network
- memory capacity(저장 용량) : Register < Cache << Main(DRAM)
                                               <<< Secondary(SSD) <<<<<<<<< Network