• CPU의 구성 요소
  

  

  • 레지스터 : 중간 데이터 저장
    • general register : 범용으로 사용하는 레지스터
    • special register : 특정 목적을 갖는 레지스터
  • ALU : Microoperation 수행
  • 컨트롤 유닛 : 동작 관리
• general register organization
  • R1 = R2 + R3
  • 연산 시 사용하는 레지스터를 각 selector가 적절히 선택

Stack Organization

• 스택 : 정보가 '쌓이는' 자료구조
  • 가장 마지막에 들어온 정보가 가장 먼저 출력됨
  • LIFO, Last In First Out
  • 스택 포인터는 스택의 가장 위(최근 들어온) 아이템을 가리킴
• push : Stack pointer를 증가(아이템 입력)
• pop : Stack pointer를 감소(아이템 출력)
• register stack
  • FULL, EMPTY, SP, DR로 구성된 스택
  • FULL, EMPTY : 스택이 꽉 찬(빈) 여부를 저장
  • SP : Stack Pointer
  • DR : 스택에 들어가거나 스택에서 나온 데이터를 저장
  • EMPTY=1일때 POP하거나, FULL=1일 때 PUSH 시 error
    • 스택의 UPPER/LOWER limit을 초과 시 오버/언더플로우 발생
  • POP시 SP를 1 감소, PUSH시 1 증가
• stack의 동작 예 : 후위 표기법
  • 후위 표기법 : 연산자가 맨 뒤로 오게 됨
  • 기존 식 : (4+5*6) / (4-2)
  • 후위 표기 : 4 5 6 * + 4 2 - /
    • 연산자는 스택 내의 숫자 2개를 pop한 후 연산 결과를 다시 push함

Instruction format

• CPU 명령어의 종류
  • 레지스터 하나만을 사용
    • ADD X : AC < AC + M[EA]
  • 다수 레지스터(general register) 사용
    • ADD R1, R2, R3 : R1 < R2 + R3
    • ADD R1, R2 : R1 < R1 + R2
    • ADD R1, EA : R1 < R1 + M[EA]
  • 주소 사용 없음(stack organization)
    • PUSH X

Addressing mode

• 명령어의 주소 필드를 해석하는 방법
• addressing mode의 목적
  • 프로그램의 다양성
  • 명령어의 address field 크기를 줄이기 위해
• address field가 필요 없는 mode
  • implied mode : Accumulator를 사용하는 연산 명령어
  • immediate mode : 명령어 필드가 주소 필드와 동일한 명령어
• Register mode : 주소 필드가 프로세서 주소를 가리키는 경우
  • register mode : 명령어가 레지스터 내에 있는 경우
  • register indirect mode : 주소 필드에 내용이 저장된 레지스터 주소를 나타내는 경우
  • autoincrement/autodecrement mode : register indirect와 동일하나 메모리 접속 이후 register이 증가/감소 (table 접근 시 사용)
• relative addressing mode
  • effective address가 PC 내용 + 명령어의 주소 필드, branch 명령에 주로 사용
  • indexed addressing mode : effective address가 index register + 주소 필드 , table 접근 시 사용
  • base register addressing mode : effective address가 base register + 주소 필드, multiprogramming에 사용

Data Transfer and Manipulation

• 명령어의 종류
• Data transfer : 데이터를 변경 없이 이동시키는것
  • memory - register
  • register - I/O
  • register - register
• Data Manipulation : 산술, 논리, shift 연산
• Program Control : branch 등 컴퓨터에 의해 프로그램 진행이 바뀌는 것

Classification

• 입력받은 데이터가 속하는 카테고리를 분류
  • 스팸 필터링
  • 의료 보조
  • 이미지 분류(Computer Vision)
• 임의 데이터셋
  

  

  • linear regression : y=ax + b꼴로 모델 형성
    • 일정 카테고리로 분류되는 데이터의 경우, linear regression 적용 시 카테고리를 크게 벗어나는 데이터에 의해 오차가 커질 위험이 있음

Logistic Regression

• 데이터가 2가지 class로 분류되었음을 가정
  • 예측하고자 하는 모델 범위는 [0, 1]
  • 클래스가 속하는 카테고리는 0 혹은 1로 구분
• $H_\theta(x)=g(\theta^Tx),\ g(k)=[1+e^{-k}]^{-1}$
  • g(k)를 signoid 혹은 logistic 함수라 부름
  • k가 무한이면 g(k)=1, -무한이면 g(k)=0
  • $\theta^Tx$ : 두 데이터 그룹을 나누는 기준선
• $P(y=1|x, \theta)=H_\theta(x)$, $P(y=0|x, \theta)=1-H_\theta(x)$
• log-likelihood $l(\theta) = log(L(\theta))\\\sum_{i=1}^m[y^ilog(H_\theta(x^i))+(1-y^i)log(1-H_\theta(x^i))]$
  • maximum log-likelihood : m=1 가정, $\frac{\partial l(\theta)}{\partial\theta_j}=[\frac{y}{H_\theta(x)}-\frac{(1-y)}{1-H_\theta(x)}]\frac{\partial H_\theta(x)}{\partial\theta_j}\\=[\frac{y}{H_\theta(x)}-\frac{(1-y)}{1-H_\theta(x)}]H_\theta(x)(1-H_\theta(x))x_j\\=(y-H_\theta(x))x_j$

Newton's method

• 최대/최소값을 찾는 방법
• f(x) = 0이 되게 하는 x를 탐색
  • $x_{t+1}=x_t-\frac{f(x)}{f'(x)}$
• $J'(\theta)$에 대해 $\theta_{t+1} = \theta_t-\frac{J'(\theta_t)}{J''(\theta_t)}$
• multiple vatiant function에 대해
  • $\vec{x_{t+1}}=\vec{x_t}-H^{-1}\nabla f(\vec{x_t})$
    • $(H_x)_{i,j} = \frac{\partial^2f}{\partial x_i\partial x_j}$ : Hessian Matrix

• Binary Classification / Logistic Regression : $\theta^Tx$가 0보다 큰가 / 작은가 여부로 분류
  • 모델 $H_\theta=g(\theta^Tx),\ g(z)=\frac{1}{1+e^{-z}}$
  • log-lokelihood $l(\theta) = log(L(\theta))\\=\sum_i[y^ilogh_\theta(x)+(1-y^i)log(1-h_\theta(x))]$
  • gradient ascent $\theta_j=\theta_j+\frac{\alpha}{m}\sum_iy^i-h_\theta(x^i))x_j^i$

Multinomial Classification

• 다수 클래스로의 분류
  • $score_j = \theta_j^Tx$
  • j개 클래스 중 가장 높은 score인 쪽으로 입력을 분류
• score normalization : [0, 1] 내의 분포로 표준화
  • $p(y^i|x^i, \theta)=\Pi_{y^i==l}[\frac{e^{\theta_i^Tx}}{\sum_je^{\theta_j^Tx}}]$
  • log-likelihood $l(\theta)=log((p(y|x, \theta))=\sum_ilog((p(y^i|x^i, \theta))))$

Exponential family

• linear, logistic, multivariant regression의 gradient descent는 동일 함수를 이용
• 이 세 함수를 같은 exponential family에 속한다고 칭함
  • exponential family : $p(y, \eta) = b(y)exp(\eta^TT(y)-a(\eta))$
• ex. linear regression
  • $p(y, \mu)=\frac{1}{\sqrt{2\pi}}exp[-\frac{1}{2}(y-\mu)^2]\\=\frac{1}{\sqrt{2\pi}}exp[-\frac{1}{2}y^2]-exp[\mu y-\frac{1}{2}\mu^2]$
  • $p(y, \eta) = b(y)exp(\eta^TT(y)-a(\eta))$ 꼴에서
  • $b(y)=\frac{1}{\sqrt{2\pi}}exp[-\frac{1}{2}y^2], T(y)=y,\ \eta=\mu,\ a(\eta)=\frac{1}{2}\mu^2=\frac{1}{2}\eta^2$
• ex. logistic regression
  • $P(y=1)=\phi$, $P(y=0)=1-\phi$
  • $P(y)=\phi^y(1-\phi)^{1-\phi}=exp[ylog\phi+(1-y)log(1-\phi)]\\=exp[ylog(\frac{\phi}{1-\phi})+log(1-\phi)]$
  • $b(y)=1,\ T(y)=y,\ \eta=log\frac{\phi}{1-\phi},\ a(\eta)=-log(1-\phi)=log(1+e^\eta)$
• Exponential family의 gradient descent
  • $\theta_j=\theta_j-\frac{\alpha}{m}\sum_i[H_\theta(x^i)-y^i]x_j^i$

• 머신러닝?
  • 명시적 프로그램 없이 학습하는 능력을 컴퓨터에게 부혀아는 것
  • 데이터를 이용한 프로그래밍

Linear Regression

• 일정 데이터의 상관관계를 선형으로 파악하는 것
• ex. 집값의 예측
  • 집의 평수와 판매 가격의 데이터가 주어짐
  • 해당 데이터를 기반으로 y = ax + b의 그래프를 작성
• 가격은 연속하여 변하는 값이므로 선형 회귀 문제로 분류된다.
• 집의 정보(입력)과 가격(출력)의 그래프를 갖고 있으므로 지도학습에 해당한다.

• 가설 $H(\theta)$ : 데이터에 기반하여 가정한 모델
  • 모델에 새 데이터를 입력시키면 예측값이 출력
  • $H(\theta) = \theta_0 + \theta_1x_1 + \theta_2x_2+...$
  • error : 해당 모델과 training data 사이의 출력(y)값 차이

• Cost Function $J(\theta)$ : 가설 H와 실제 데이터 y 사이의 차이
  • 예측 모델의 정확도를 표현
  • J가 0이면 완벽한 예측임을 의미
  • $J(\theta) = \frac{1}{2}[H(\theta) - y]^2$
    • 최솟값의 계산 : $\theta$에 대한 미분값이 0이 되는 지점을 탐색
• $\frac{\partial J(\theta)}{\partial \theta_i}=[H(\theta) - y]\frac{\partial H(\theta)}{\partial\theta_i}=[H(\theta)-y]x_i$
  • parameter update : $\theta = \theta - \alpha\frac{\partial J(\theta)}{\partial\theta}$ ($\alpha$ : running rate, 값이 변화하는 정도)
• non-convex한 경우 : 미분값이 0이 되어도 최소가 아닐 수 있음

• gradient descent : parameter update시 모든 오차값의 합을 이용해 갱신
  • 데이터가 많은 경우 속도가 느린 단점
  • 수렴할 때까지 : $\theta_j = \theta_j - \alpha\sum_{i=1}^m[H(\theta_j)-y^i]x_j^i$
• stochastic descent
  • gradient descent의 경우 모든 feature의 변화값 합을 계산하므로 연산 부담이 높음
  • stochastic의 경우 각 feature마다 weight 변화를 갱신하므로 연산 부담이 상대적으로 낮음
  • $\theta_j = \theta_j - \alpha[H(\theta_j)-y^i]x_j^i$ for all i

Normal Equation

• $\frac{\partial J(\theta)}{\partial\theta_i}=0$
  • 행렬 미분 : 각 원소에 대해 함수를 편미분
  • $\nabla_AF(A)=\begin{bmatrix} \frac{\partial F(A)}{\partial a_{11}} ... \frac{\partial F(A)}{\partial a_{1n}}\\ ...\ \ \ \ \ \ \ \ \ \ \ ...\\ \frac{\partial F(A)}{\partial a_{n1}} ... \frac{\partial F(A)}{\partial a_{nn}} \end{bmatrix}$
• $H(\theta) = X\Theta$로 표현 가능
  • $X = \begin{bmatrix} 1 x_1 x_2 .... x_n \end{bmatrix}$, $\Theta = \begin{bmatrix} \theta_0\\ \theta_1\\ ...\\ \theta_n \end{bmatrix}$
  • $\nabla_\theta J(\theta) = \frac{1}{2}\nabla_\theta[X\Theta - Y]^T[X\Theta - Y]$
  • $X^T[Y-X\hat{\Theta}]=0$
    $\rArr\hat{\Theta}=[X^TX]^{-1}X^TY$

Polynomial Regression

• Linear Regression : $H(\theta) = \theta_0 + \theta_1 x_1$
• Polynomial Regression(2nd-order) : $H(\theta) = \theta_0 + \theta_1 x_1 + \theta_2 x_1^2$
• Feature Scaling
• 함수의 각 feature들이 비슷한 범위를 갖도록 함
  • feature 범위가 달라지게 되면 각 feature가 결과에 영향을 주는 정도가 달라질 수밖에 없기 때문
  • mean normalization : $x = \frac{x-\mu}{S}$ (S는 범위 혹은 표준편차)
• Other regression
  • multiple regression : 2차 이상의 비선형 데이터에 대한 회귀
  • locally-weighted linear regression : 특정 부분에만 multiple linear model 구현

Probablistic Interpretation

• 예측값 $y^i$ 가정
  • $y^i=\theta^Tx^i+\epsilon^i$
  • $\epsilon$은 오차 ($\epsilon \sim N(0, \sigma^2)$)
    • 오차 $P(y^i|x^i, \theta) \sim N(\theta^Tx^i, \sigma^2)$
  • 전체 dataset의 오차 : $P(Y|X, \Theta) = \Pi_{i=1}^n p(y^i|x^i, \theta)$
    • $P(Y|X, \Theta) = L(\Theta)$ : Likelihood - parameter 변경 시 X에 대해 Y의 확률

Deadlock

• 데드락의 발생 조건
  • Mutual Exclusion : 프로세스 간 자원의 공유(동시 사용)이 불가
  • Hold and Wait : 자원을 한 프로세스가 점유한 경우, 다른 프로세스 접근 시 대기
  • No Preemption : 점유한 자원은 반환하기 전까지 해당 프로세스가 계속 사용
  • Circular wait : 프로세스는 다음 프로세스의 자원을 대기
    • Pa > Pb, Pb . Pc, ... Pz > Pa

• Resurce Allocation Graph
  

  

  • 자원의 할당 방향을 표현
  • P : Process, R : Resource, T : Thread
  • 자원 요청 : P에서 R로 화살표
  • 자원 할당 : R에서 P로 화살표
  • R 내의 점 : Resource가 갖는 인스턴스를 의미
• Circular wait에 의한 데드락 발생 조건
  • Cycle 없음 : deadlock x
  • Cycle 있음 : 리소스 내에 인스턴스가 복수개 있을 경우 deadlock x

Handling deadlock

Deadlock Prevention

• Mutual Exclusion - 자원의 공유 허용
• Hold and Wait
  • 프로세스 시작 전에 자원을 미리 할당
  • 자원을 미리 할당해야 하므로 활용성이 떨어지거나, starvation 위험
• No preemption - 자원 선점 허용
• Circular Wait - 자원에 lock 요청 시 우선순위 배정

void transaction(account from, account to, double amount){
  mutex lock1, lock2;
  lock1 = get_lock(from);
  lock2 = get_lock(to);

  acquire(lock1);
  acquire(lock2);
  //from이 먼저 lock acquire

  withdraw(from, amount);
  deposit(to, amount);
  release(lock2);
  release(lock1);
}

Deadlock Avoidance

• 각 프로세스가 요구하는 자원 정보가 필요
• 시스템이 deadlock 진입 여부를 확인한 후 자원을 할당
• safe state : 자원 할당 시 deadlock이 발생하지 않는 상태
• unsafe state : deadlock이 발생할 가능성이 있는 상태
• avoidance algorithm
  • resource-allocation graph
    • 리소스당 인스턴스가 하나인 경우
    • Claim edge : 프로세스/스레드 할당 시 필요 자원을 OS에 요청
    • Claim edge > request > assignment > claim > ...
    • claim edge를 이용하여 요구 자원이 사용중인지 여부를 판단해 deadlock 방지
  • Banker's Algorithm
    • 리소스당 인스턴스가 다수 존재
    • 각 프로세스는 OS에 사용 자원을 알려야 함
    • 자원 부족시 대기
    • 프로세스 실행 후 일정한 시간 후 자원을 반납
    • banker's algorithm의 자료구조
      • available : 사용 가능한 인스턴스를 저장하는 vector
      • max : 리소스 당 사용 가능한 자원을 나타내는 matrix
      • allocation : 각 프로세스가 점유한 자원을 나타내는 matrix
      • Need : 프로세스 완료를 위해 필요한 자원을 나타내는 matrix
        • neet = max - allocation

• safety algorithm
  1. 변수 선언
  • work = available
  • finish[i] = false: 프로세스가 끝났는지 여부
  2. i에 대해서
  • finish[i] = false
  • need[i] <= work인 프로세스 탐색
  • 존재하지 않는경우 4로
  3. 자원 반납
  • work = work + allocation
  • finish = true
  • 2 반복
  4. finish[i] == true인 경우, 시스템은 safe state
• resource request algorithm
  • request_i[j] : 프로세스 i의 request vector
    • request_i[j]=k : 프로세스 i는 resource j의 k개 인스턴스를 필요로 함
  • request_i <= need면 진행, 그렇지 않은 경우 error(최대 제한을 초과)
  • request_i <= available이면 진행, 그렇지 않은 경우 자원 할당이 불가하므로 대기
  • 자원 할당
    • available = available - request
    • allocation = allocation + request
    • need = need - request
    • safe인 경우 자원 할당, unsafe인 경우 대기

Deadlock Detection

• deadlock 감지 및 복구
• wait-for-graph
  

  

  • resource allocation graph에서 resource가 빠진 방식
  • cycle 감지 시 n개 프로세스에서 n^2개의 계산 동작이 필요
• detection algorithm
  1. 변수 선언
  • work = available
  • allocation_i != 0인 경우 finish_i = false, 그렇지 않은 경우 true
  2. i에 대해
  • finish[i] == false
  • request_i<=work인 프로세스 탐색
  • 존재하지 않는 경우 4로
  3. work = work + allocation, finish[i] = true, 2 반복
  4. finish[i] == false인 경우 i번째 프로세스는 deadlock

Deadlock recovery

• deadlock된 모든 프로세스를 제거
• deadlock이 풀릴때까지 프로세스를 하나씩 제거
• 프로세스를 rollback
  • rollback당한 프로세스는 starvation 위험이 존재

Control Memory

• Microoperation의 순서를 제어
• 다른 명령어 = 다른 Microoperation
• Hardwired Control : 논리회로 설계에 의한 signal contol
• Microprogram : SW적으로 signal control
  • 메모리에 control 신호를 저장하여 호출
  • hardwired 대비 유연한 제어가 가능하다
• control function
  • LD, INC, CRL 등 binary information (Control word라고 부름)
  • control word는 control memory 내에 저장

Address Sequencing

• Control Unit을 Control Memory + 메모리 순회를 위한 Logic으로 대체

  • Control Address Register : Control Memory를 가리키는 register

    

• MicroOperation의 동작

  • 명령어 Fetch-Decode 후 실제 명령어가 동작
  • Opcode 값에 의해 동작 내용이 달라짐

• Instruction Mapping

  • opcode를 memory 주소 형식으로 바꾸는 것
  • ex. opcode가 XXXX >> 0XXXX00의 형태로 address 반환

• HW configuration Example
  

  

  • 버스를 사용하지 않음
  • IR 레지스터가 없음
  • AC, PC, 메모리 > DR
  • PC, DR > AR
  • AR > PC
  • DR > 메모리
  • DR, AC의 Microoperation 결과 > AC
• 명령어는 I(1) + Opcode(4) + Address(11)로 구성되어있음을 가정
  • Add(0000), Branch(0001), Store(0010), Exchange(0011, AC와 Memory 데이터를 교환)의 4가지 명령어를 가정
• Control Word Format
  • F1/F2/F3 (각 3bit) : Microoperation field
  • CD(2bit) : Branch Condition
    • 00 : always
    • 01 : Indirect
    • 10 : AC sign bit
    • 11 : AC zero
  • BR(2bit) : Branch field / CD 조건 만족시 동작
    • 00 : JMP
    • 01 : CALL
    • 10 : Return
    • 11 : Map
  • AD(7bit) : Address field
  • 총 20bit 크기

Microprogram example

• fetch routine
  • PCTAR U JMP NEXT : PC 정보를 AR로, 다음 명령 수행
  • READ, INCPC U JMP NEXT : 메모리 정보를 DR로 읽고, PC를 1 증가시킨 후 다음 명령 수행
  • DRTAR U MAP : DR 정보를 AR로 이동시킨 후, DR opcode를 CAR에 메모리 양식에 맞게 Mapping
• Add
  • NOP I CALL INDRCT : 동작은 하지 않고, Indirect인 경우 INDRCT 주소를 불러온다.
  • READ U JMP NEXT : 메모리 값을 AC로 불러온 후 다음으로 진행
  • ADD U JMP FETCH : DR값을 AC에 더해준 후 FETCH operation으로 이동
• Microprogram sequencer
  

  

  • CD값과 1, I, S, Z에 따라 Test 출력 결정 (1 = Unconditional Branch)
  • I0, I1 : Branch code

Machine Language

• 어셈블러 : Symbolic한 코드(어셈블리어)를 기계어로 바꿔줌
  • ex. 1 ADD 56 > 1 000 0000 0011 1000
• 컴파일러 : 고급 언어(C, Java, ...)를 기계어로 바꿔줌

Assembly Language

• 어셈블러 : Symbolic Program을 기계어로 변환
• 기계마다 기계어가 다르므로, 어셈블러 역시 기계마다 다르게 동작
• 어셈블리 명렁어의 구성요소
  • Lable : 공백 or Symbolic Address
    • Symbolic Address
      • 알파벳 형태로 주소 지정
      • 첫 글자는 반드시 대문자로 써야 하며, 콤마(,)로 종료
  • Instruction : machine / pseudo Instruction
    • pseudo instruction
      • ORG(Origin of Program), DEC(Decimal), END(END of program) 등
      • 실제 동작에는 관여하지 않고, 어셈블러 동작에 필요한 정보 지정
    • MRI(Memory Reference Instruction)의 경우 공백으로 구분되는 Symbol 명령어
      • 명령어 + 주소 (+ Indirect)로 구성
      • ex. ADD OPR / ADD OPR I (Indirect MRI)
    • non-MRI : 1개 Symbol ex. CLA(Clear ACC)
  • Comment : 코드 주석
• Code Example : subtract code
  

  

  

  • ORG 100 : 100번 주소에서 코드 시작
  • LDA SUB : SUB 명령어를 Load
    • SUB 명령어는 107에 저장되어 있음
    • SUB의 Opcode가 010이므로 Hex Code 2107로 표현됨
    • MIN : 계산할 값
    • SUB : 뺄 값
    • DIF : 차이
  • CMA - INC - ADD MIN
    • 2진수 빼기는 2의 보수(1의 보수 + 1)을 더하는 방식으로 진행
  • STA DIF : DIF 주소(108)에 결과 저장
  • HLT : 컴퓨터 종료
  • END : 코드의 끝

Numpy

• 과학 계산의 경우 행렬 연산의 비중이 높으며, 이를 효율적으로 처리하기 위해 사용되는 라이브러리

import numpy as np

np.arange(10)
# array([0,1,2,3,4,5,6,7,8,9])

Scalar

• 단일 값으로 표현
  • pi, 온도, x, y 등등...
• 스칼라값은 소문자 알파벳으로 표현 (a,b,c,d,...)

Vector

• 값으로 이루어진 array
• column vector : $x = \begin{bmatrix} x_1\\ x_2\\ x_3\\ ... \end{bmatrix}$
• row vector : $x = \begin{bmatrix} x_1, x_2, x_3, ... \end{bmatrix}$

Matrice

• 값으로 이루어진 2차원 배열
• $x=\begin{bmatrix} x_{11},x_{12}, ..., x_{1m}\\ x_{21},x_{22}, ..., x_{2m}\\ ...\\ x_{m1},x_{m2}, ..., x_{mm}\\ \end{bmatrix}$
• 머신러닝에 있어서 많은 데이터는 벡터나 행렬로 표현
• matrix 생성 함수
  • np.array([list]) : list를 numpy 배열로 변환
  • np.arange(n) : 0~n-1의 배열 생성
  • np.reshape(r,c) : r x c 크기로 배열 재생성
  • np.zeros(size) : 0행렬 생성
  • np.ones(size) : 모든 원소가 1인 행렬 생성
  • np.full(size, element) : 해당 행렬을 element로 채움
  • np.random.random(size) : 0 ~ 1 사이의 값을 원소로 갖는 행렬 생성
  • Transepose(행렬) or 행렬.T : 행렬의 행-열을 바꿈
  • np.shape() : (행, 열) 반환
  • len(arr.shape) : 몇차원 행렬인지를 반환

Tensor

• 2개 이상의 축을 갖는 행렬
  • ex. RGB image(가로, 세로 x 3 (R, G, B))
• tensor 연산 : 일반 연산과 동일하게 작성
  • 곱셈, 나눗셈은 행렬곱이 아닌 원소 간의 곱으로 계산
• reduction
  • 원소들의 합을 계산하고, 1개 축을 제거
  • tensor.sum()
    • axis 미지정시 전체 원소의 합
    • axis : 0인 경우 세로 방향의 합을, 1인 경우 가로 방향의 합 계산
    • keepdims : 합을 계산 후 배열 크기를 유지
• np.identity : 단위행렬 반환
• np.diag : 대각행렬 반환
• np.dot(vec1, vec2) : 행렬의 합성곱($\sum x_1 \times x2$) 계산

Norm

• 벡터를 스칼라를 연결
  • 벡터의 크기에 대한 표현
• norm f의 특징
  • $f(ax)=|a|f(x)$ : vector에 상수를 곱한 만큼 증가
  • $f(x+y)\leq f(x)+f(y)$
  • $f(x)\geq 0$ : norm은 항상 0 이상
• $L_p-norm$ : $||x||_p=[\sum^n_{i=1}|x_i|^p]^{1/p}$
  • L1 norm : manhattan distance ( 절대값의 합 )
  • L2 norm : Euclidian distance

파이썬 프로그램의 실행

• 파이썬은 인터프리터 언어이므로, 기본적으로는 맨 처음부터 시작하게 됨
• 프로그램 시작점이 필요한 경우(main), 다음과 같이 정의

def main():
  # 수행할 main함수 내용

if __name__ == '__main__' :
  main()

파이썬 모듈

• import 이름 형태로 불러옴
• from package import 모듈 : 패키지(모듈) 내의 구성요소를 바로 불러올 수 있음
  • 사용자 함수와 동일한 모듈을 불러온 경우 오류 위험

import math # a
from math import cos # b

# a의 경우
math.cos(0)

# b의 경우
cos(0)

• 모듈을 import해도 하위 모듈까지 같이 import되지는 않으므로 호출해주어야 함

import A
'''
module A
ㄴmodule B
    ㄴmodule D
ㄴmodule C
일때, A를 import한다고 B,C,D를 바로 쓸수 없다
'''
A.B #(o)
B #(x)
A.B.D #(o)
B.D #x

• absolute import
  • 파이썬의 환경변수(sys.path)에 속하는 경로 모듈에 접근
• reletive import
  • 작성된 프로젝트에 속하는 모듈에 접근
• init.py : 패키지의 초기화
  • 패키지 import 시 가장 먼저 실행됨
  • __all__변수 : from ... import * 명령(패키지 내 모든 구성요소 import) 실행 시 가져오는 내용

• sys 모듈
  • 인터프리터에 의해 사용되는 정보, 변수
  • sys.argv : 커맨드라인으로 실행 시 매개변수 호출
  • ex. pyhon foo.py file.txt
    • argv[0] == "foo.py"
    • argv[1] == "file.txt"

Background

• Data consistency
  • 멀티프로세싱/스레딩 시에 다수 작업이 동시에 시행
  • 인터럽트 발생 시 이전에 동작하던 작업이 일시 중단되고 새로 실행
  • 여러 작업이 데이터를 공유할 경우 문제 발생
    • 데이터 업데이트 중 다른 프로세스가 읽어들이거나
    • 여러 프로세스가 동시에 쓰는 경우
  • 일정 루틴에 맞는 프로세스 실행 순서를 정의할 필요가 존재
• Producer - Consumer Problem
  • 데이터 생산 프로세스(Producer)는 큐가 차있지 않은 동안 데이터를 입력
  • 데이터를 쓰는 프로세스(Consumer)는 큐가 비어있지 않으면 데이터 사용
  • Counter 변수를 같이 접근하는 문제 존재
    • ++, --명령어 실행 시 변수값을 각 레지스터로 이동하여 처리
  • race condition : 초기값이 5일 때, 동시에 접근 시 Producer는 5 > 6, Consumer는 5 > 4로 Counter 값을 바꾸므로 결과적으로 카운터값이 6>4로 변경될 가능성 존재
  • fork()의 race condition
    • fork 실행 시 반환값은 PID
    • 두 프로세스가 동시에 fork 호출 시 같은 PID를 갖는 두 프로세스가 생성될 수 있음

/*  Producer Process  */
while (true) {
/* produce an item in next produced */
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}

/*  Consumer Process  */
while (true) {
while (counter == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}

Critical-Section Problem

• 다수의 프로세스/스레드 생성 시 한 번에 하나의 작업만 실행될 수 있는 구간
  • 공용 데이터 접근시의 충돌 방지

do
{
    /* Ask Permission to enter critical section */
        /*  Critical Section */
    /* Exit Critical Section */
    ...
}while(...);

• Critical Section 문제의 해결 조건
  • Mutual Exclusion : 프로세스 P가 Critical Section에 접근 시 다른 프로세스는 해당 구간을 실행하면 안됨(Critical Section의 정의)
  • Progress : Critical Section에 실행 중인 프로세스가 없을 경우, 이 구간에 진입하고자 하는 프로세스를 지연 없이 진입시켜야 함
  • Bounded Waiting : 프로세스 A가 Critical Section에 있을 때, 새 프로세스가 진입하고자 할 경우 A가 끝나는 것을 대기해야 하나, 무한정 대기해서는 안됨 (Critical Section 진입 시 우선순위의 조정 필요)
• OS의 Critical-Section Handling : Non-Preemptive
  • 인터럽트 없이 커널 설계
  • 구현이 쉽고, 오류를 신경쓸 필요성이 낮아짐
  • 공유 데이터 접근 시 우선한 작업이 처리되어야 나머지 처리가 가능하므로 시스템 반응성, 성능이 떨어지게 됨

Peterson's Solution

• SW 기반으로 HW 영역의 문제를 해결하고자 하는 접근법
• 2개 프로세스/스레드를 가정
  • load/store 명령어는 순서대로 실행된다고 가정(각 명령어 중에는 인터럽트가 없음)
  • 두 프로세스에는 변수가 존재 : int turn ; bool flag[2]
  • turn : critical section에 접근 가능한 프로세스
  • flag[i]가 true면 i번째 process가 Critical section에 접근하고자 함

• Entry Section
  • 자신의 flag를 true로 만듦 : critical section에 접근할 준비
  • turn을 상대 프로세스 값으로 대입
  • while : 상대 프로세스가 준비가 되었고(flag), 실행할 순서인 경우(turn), 완료할 때까지 무한루프로 대기
    • 그렇지 않은 경우 자신의 코드 실행
  • critical section 실행 후 자신의 flag를 false로 설정
• 위 예시의 검증
  • Mutual Section : while문 조건에서 turn이 상대방 값으로 대입되므로 critical section에 동시 접근이 불가
  • Progress : Entry section에 진입하지 않은 경우 해당 프로세스의 flag는 false이므로 다른 프로세스는 바로 critical section에 접근 가능
  • Bounded Waiting : turn이 상대 값으로 대입되었기 때문에 프로세스가 while문 재진입 시 다른 프로세스에 우선권을 넘겨주므로 무한 대기 없이 두 프로세스가 순차 실행

• Peterson's Soultion의 문제 : 현대 컴퓨터에서 실행을 보증하지 않음
  • 프로세서나 컴파일러가 성능을 위해 독립적으로 실행되는 명령어 순서를 변경할 수 있음
  • 독립적인(서로 다른 곳에 접근하는) 명령어의 경우 순서를 바꾸어도 결과는 동일
  • 멀티코어 / 멀티프로세서 구조에서 심각한 문제가 될 수 있음

    

    • 원래의 알고리즘
      • (Process i) flag i = true, turn = j
      • (Process j) flag j = true, turn = i
      • (Process j가 먼저 접근한 경우) j는 critical section 처리, i는 while 대기
      • flag j = false : Process i가 critical section 처리
    • 현대 아키텍처의 경우
      • (Process i) turn = j : flag를 나중에 대입
      • (Process j) turn = i, flag j = true
      • turn i=false이므로 Process j가 Critical section 처리
      • (Process i) flag i = true
      • turn이 i이므로 Process i도 Critical Section에 접근 가능 : Mutual Section 위반

HW Support for Synchronization

• Critical Section Code를 위한 별도 명령어 제공
  • Memory Barrier
  • HW Instruction
  • Atomic Variable
• Memory Barrier
  • 명령어의 실행 순서를 명시
  • Strongly Ordered : 각 프로세서가 구현 명령어대로 접근
  • Weakly Ordered : 명령어 접근 순서가 바뀔 수 있음
  • Memory barrier : 배리어 전후로는 명령어 순서 변경이 불가
• HW Instruction
  • Test-and-Set

    boolean test_and_set (boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv:
    }

    • 다른 명령어와 독립적으로 실행(execute atomically)
    • target값을 읽어들인 후, target에 새 값 대입
    • 읽어들인 값 rv 반환
  • Compare-and-Swap

    int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
    *value = new_value;
    return temp;
    }

    • 이전값(value)가 예측값(expected)와 동일하면 새 값(new_value)로 치환

// criticals section with test_and_set
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);

• test_and_set이 처음에는 false
  • 먼저 접근한 프로세스가 lock을 true로 바꿈
  • 나머지 프로세스들은 test_and_set이 true를 반환하게 되므로 mutual section이 성립

//critical section with comp_and_swap
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}

• 초기값 lock이 0이면 해당 프로세스는 Critical section 진입하면서 lock을 1로 바꿈
  • 나머지 프로세스는 lock이 1이므로 while 대기
  • 이때 value와 expect가 다르므로(1, 0) swap이 되지 않게 됨

while (true) {
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
        key = compare_and_swap(&lock,0,1);
    waiting[i] = false;
    /* critical section */
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = 0;
    else
        waiting[j] = false;
/* remainder section */
}

• Bounded waiting and Mutual section
  • i번째 프로세스가 실행된 경우
  • i+1부터 순회하면서 대기중인 프로세스 탐색
  • 대기중인 프로세스가 있을 경우 해당 프로세스의 waiting 상태를 풀어줌
  • 특정 프로세스가 계속해서 점유하는 것을 방지
• Atomic Variable
  • 변수 하나만을 보호해야 할 경우
  • 동시 접근 시 데이터의 일관성 보장

Mutex Locks

• acquire/release 명령어로 atomic variable 선언
  • busy wait : Critical Section에 접근하지 못한 나머지 변수들은 while loop를 돌면서 대기
  • spin lock : 무한루프를 돌면서 대기하는 형태(busy wait)

Semaphores

• Mutex Lock의 경우 한 번에 하나의 프로세스만 Critical Section 진입
• Semaphore의 경우 정수 변수 S 값의 설정에 따라 진입 가능한 프로세스 수 설정 가능
  • wait(S) : 대기 중인 프로세스 조정
  • signal(S) : 실행이 완료된 프로세스 release
• 자원 관리에 주로 사용
• Busy wait이 없는 Semaphore
  • 프로세스 sleep(), wakeup() 확인
  • wait : 프로세스 실행이 불가능한 경우 프로세스를 sleep queue에 추가 후 sleep
  • signal : 프로세스가 추가 실행이 불가능하면서 waiting중인 프로세스 존재 시 해당 프로세스 wakeup
  • 프로세스 리스트 접근 시 mutex section 구현 필요

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
    //add this process to S->list;
    block();
    }
}
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
    //remove a process P from S->list;
    wakeup(P);
    }
}

Monitor

• mutex/semaphor의 고레벨 구현
• monitor 내에 선언한 함수는 컴파일 단계에서 wait-signal이 구현됨
• condition variable
  • 변수에 여러 프로세스가 동시 접근 시 signal - wait 구현

Liveness

• Progress, Bounded Waiting으로 보장
• 프로세스가 일정 시간 내에 실행되는 것을 보장
  • 보장되지 않을 경우 알 수 없는 이유로 시스템이 멈추는 등의 문제 발생
• Deadlock
  • 둘 이상의 프로세스가 서로의 자원을 필요로 하는 상황
    

    

  • 서로의 wait을 위해 서로의 자원을 필요로 하는 상황
    • P0의 Q wait을 위해서는 P1이 대기하는 Q가 필요
    • P1의 S wait을 위해서는 P0이 대기하는 S가 필요
• Starvation
  • 프로세스가 공유 자원(Critical Section, Semaphore, ...)을 무한히 대기하는 현상
  • 선점한 프로세스가 무한히 자원을 점유하기 때문에 발생
• Priority Inversion
  • P1>P2>P3의 우선순위를 갖는 프로세스(P1이 가장 우선)을 가정
  • P1, P3이 공유 자원 R1을 사용하는 상황
  • P3이 사용하는 자원을 release해야 P1을 실행 가능
  • 이때 P2가 실행되면 P2>P3이므로 P2가 우선 실행
  • P1은 R1 자원을 대기중이므로 실행되지 못함
  • 이로 인해 P2가 P1보다 우선 실행되는 우선순위 역전 현상이 발생
  • 해결책 : Priority Inheritance(우선순위 상속) - P3의 우선순위를 P1 수준으로 높여줌

Bounded-Buffer Problem

• n개의 버퍼마다 데이터 존재
  • 버퍼에는 full, empty, mutex 변수를 갖고 있음
  • full : 버퍼 내 데이터 수
  • empty : 버퍼 내의 공백 수 (full + empty = 버퍼 크기)
  • mutex : 프로세스의 권한 할당 여부 (1 - producer / 0 - consumer)
• Producer
  • 버퍼가 비었는지 확인(wait(empty))
  • lock acquire - release acquire(wait, signal(mutex))
  • notify consumer(signal(full))
• Consumer
  • 버퍼가 찼는지 확인(wait(full))
  • lock acquire - relase acquire(wait, signal(mutex))
  • notify producer(signal(empty))

Readers-Writers Preoblem

• readers : 데이터를 읽기만 하는 프로세스
• writers : 데이터의 입/출력을 모두 하는 프로세스
• readers의 경우 동시에 데이터 읽기가 가능하게 설정
  • rw_mutex semaphore를 설정

파이썬 연산자

• 산술 연산자
  • =: 할당
  • +, -, *, / : 사칙연산
  • // : 정수 나누기(5//2 = 2)
  • % : 나머지
  • ** : 거듭제곱
  • >>, << : bit shift left, right
  • &, |, ~, ^ : bit and, or, not, xor
• 파이썬의 비교 연산자
  • A>B, A>=B : A가 B보다 크다 / 크거나 같다
  • A<B, A<=B : A가 B보다 작다 / 작거나 같다
  • A==B, A!=B : A와 B가 같다 / 다르다
  • not A : A가 아닌 경우
  • A and B, A or B : A 그리고/혹은 B
  • 모든 비교 연산자는 true 혹은 false를 반환

파이썬의 제어문

• 파이썬 제어문은 들여쓰기(space, tab)으로 해당 영역을 구분함
• 둘을 혼합해서 사용할 수는 없음
• if : 조건문

if ''' condition 1 ''':
    # TODO
elif ''' condition 2 ''':
    # TODO if condition 1 not satisfied
...
else :
    # TODO if all condition not satisfied

while, for : 반복문

while ''' condition ''':
    # while condition satisfied, TODO

for i in [1, 2, 3]:
    # loop(iterate) all element in list

• range(start, end, step)
  • start부터 end-1까지를 step 단위로 반복
  • range(5) = [0,1,2,3,4]
  • range(1,5) = [1,2,3,4]
  • range(1, 10, 2) = [1,3,5,7,9]
  • range(10,1,-1) = [10,9,...,3,2]

파이썬 함수

• 추상화를 위한 도구 : 입력과 출력 사이의 동작 내용은 Blackbox화
• 특정 기능을 구현하는 코드 영역
• 프로그램의 기본적인 단위(block)
• 코드의 재사용이 가능하게 함
• local scope : 함수 내의 변수는 외부에 영향을 주지 않음

def func1(arg1, arg2): #function header
    return arg1+arg2   #function body

#####
a = 4
def test():
    a = 5
    print(a) # 5

print(a) #4

• parameter : 함수 호출 시 전달하는 값
  • positional parameter : 전달 순서에 따른 값 할당
  • default value : 함수 선언 시 매개변수에 값을 대입하면 함수 호출시 값 전달을 하지 않아도 호출 가능
  • variadic positional argument : 정해지지 않은 개수의 파라미터를 튜플 형태로 전달
  • variadic keyword argument : 정해지지 않은 개수의 파라미터를 딕셔너리 형태로 전달

#positional parameter
def mul(a,b):
    return a*b

mul(1,2) #a=1, b=2
mul(2,1) #a=2, b=1

# default value
def mul(a,b=1):
    return a*b

mul(1,2) #a=1, b=2
mul(1) #a=1, b=1(default)


# variadic positional argument
def mul(*args):
    for a in args:
        print(a)

mul(1,2,3,4,5)

#variadic keyword argument
def mul(**args):
    for key, value in args:
        print(key, value)

mul(a=1, b=2, c=3, d=4)

• variable scope
  • 함수 내외의 변수는 독립적으로 취급됨
  • global : 최상위 변수에 접근
  • nonlocal : 자신의 상위 scope에 해당하는 변수에 접근

x = 1 # (a)
def A():
    x = 2 # (b)
    def B():
        nonlocal x = 3 #(c)
        global x = 3 #(d)

# (c)의 경우, (b)에 접근
# (d)의 경우, (a)에 접근

람다식

• 파이썬 함수는 일종의 객체
• 람다식 = 익명 함수
  • lambda arg1, agr2, ... : 계산식

sums = lambda x, y, z : x+y+z

파이썬의 클래스

• 객체지향 프로그래밍 : 동작을 정의하는 데이터와 코드를 객체 형태로 표현
• 객체지향의 특징
  • Encapsulation
    • 사용하는 데이터 접근 시 함수를 사용
    • 객체 내부의 동작은 내부에서 접근 불가
    • 디버깅을 용이하게 함
  • Abstraction
    • 디자인 관점의 문제
    • 내부의 복잡한 동작보다 문제의 핵심에 집중
  • Inheritance
    • 각 객체의 공통 특성을 상위의 하나의 객체에서 상속
    • ex. 세단, SUV, 트럭은 모두 차량이라는 공통 특성을 보유
    • 파이썬의 경우 다중 상속을 지원
  • Polymorphism
    • 같은 이름을 갖는 기능이 여러 동작을 하는 것
    • ex. sort - bubble sort, quick sort, ...
• 파이썬의 클래스 정의
  • constructor : 클래스 생성 시 자동으로 호출되는 함수로 객체를 초기화
  • 객체는 클래스의 인스턴스로 선언됨

class Car:
    num_of_cars = 0 #class variable
    def __init__(self, hp): # constructor
        Car.num_of_cars+=1
        self.hp = hp
    
    def accelerate(self): # member method
        ...

car = Car(100)

• getter/setter : 인스턴스 외부에서 접근하기 위한 방법 제공
  • getter는 변수값을 읽을 때, setter는 변수값을 쓸 때 활용
• 클래스 변수와 인스턴스 변수
  • 인스턴스 변수 : 객체 생성마다 선언되는 변수
  • 클래스 변수 : 해당 클래스가 공유하는 변수
  • 인스턴스 변수 접근 시 존재하지 않는 경우 클래스 변수 탐색
• @staticmethod : 객체가 아닌 클래스에 작용하는 메소드
• @classmethod : 클래스와 무관하게 객체에만 작용하는 메소드

Exception

• 오류를 처리하기 위한 방법
• Try-Except문을 이용해 처리
• else : except가 발생하지 않은 경우
• finally : except와 무관하게 무조건 실행
• 파이썬 Exception은 계층적으로 구성
  • 최상위에 BaseException으로 구성
  • 가장 많이 쓰는 예외들은 Exception 클래스 내에 존재
• 사용자 정의 Exception
  • 클래스 상속을 통해 정의
  • class MyError(Exception) - raise MyError("info") - except Myerror as e : print(e)