.png)
Jonathan E. Steinhart 의 ＜한 권으로 읽는 컴퓨터 구조와 프로그래밍＞을 읽고 정리하는 온라인 책터디.
매주 2 챕터씩 진행합니다.
요약된 내용은 모두
Jonathan E. Steinhart. (2021). 한 권으로 읽는 컴퓨터 구조와 프로그래밍(오현석, 역). 경기: 책만. (원서 2019년 발행)>>> 책터디 _6주차
11장 성능 향상을 위한 알고리즘 기법
계산을 피하는 두가지 방법. 지금길shortcut과 근삿값 계산approximating
컴퓨터의 계산 자원을 효율적으로 사용한다는 말은 필요보다 더 많은 계산을 수행하지 않는다는 것.
표 찾기
직접 계산보다 표에서 찾아내기가 더 빠른 경우.
미리 계산 뒤 반복 사용이 합리적이라는 면에서, 8장 루프 불변값 최적화와 비슷.
- 변환
Ex) 온도와 전압의 관계를 예로 보면, 곡선의 관계. 공식은 계산 비용이 비싼 자연로그 등 이므로. 계산을 생략하자.
-> 모든 계산을 없애기 위해 1,024바이트짜리 표가 있으면 된다.
- 텍스처 매핑(texture mapping)
비디오 게임이나 영화 등에서 이미지를 만드는 텍스처 매핑에도 표 찾기 기법이 중요 역할.
MIP 매핑 : 뉴욕 공과대학 그래픽 언어 실험실의 랜스 윌리엄스(Lance Williams)가 고안.
32비트 시스템에서 3색을 나열하면 1/4 공간 낭비에 주목. 남는 공간에 이미지의 복사본을 계속 넣는 방식.
자주 사용할 정보를 미리 계산해 두는 것. 저해상도 텍스처. 는 루프 불변값 최적화와 비슷하다.
- 문자 종류 판별(character classification)
어떤 글자가 숫, 문자 등 어떤 분류에 속하는지 판별하는 문자 종류 판별은 어휘 분석에서 중요한 부분.
-아스키 코드 표를 작성하는 세가지 문자 종류 판별 코드의 방법
정수를 사용한 계산 방법
- 정수 덧셈, 뺄셈.
- 곱셈, 나눗셈.
- 부동소수점 연산.
- 삼각함수, 로그(대수)함수 계산.
순으로 하드웨어에서 연산속도, 전력소모 측면에서 비용이 많이 든다.
변환(transformation) : 현대 컴퓨터 그래픽 시스템들은 이믜로 좌표계를 변환하도록 지원
Ex) 모든 (x,y) 좌표에 대해 변환을 적용하여 화면 좌표(x', y')로 변환(affine).
x' = Ax + By + C
y' = Dx + Ey + F
C 와 F : 평행이동(translation)에 쓰인다. 물체의 각 점을 축 방향으로 나란히 움직인다.
A 와 E : 크기 변환(scaling)에 기여. 물체의 크기 확대 하거나 축소.
B 와 D : 회전(rotation)에 기여. 물체를 돌린다.
이를 행렬 형태로 표현할 수도 있다.
재귀적 분할(recursive subdivision)
재귀적 분할을 사용해 최소한의 작업으로 목적 달성하는 방법
- 나선
자바스크립트 등에서 제공하는 수학 라이브러리에 있는 삼각함수는 도가 아니라 라디안(radian, π) 단위로 각도를 입력 받는다.
- 구성적인 기하
쿼드트리에 불리언 함수를 적용하면 간단한 기하학적 요소를 복잡한 모양으로 만들수 있음
구조적 입체 기하(constructive solid geometry) : 3차원은 2차원보다 노드가 2배 더 필요. 쿼드트리를 옥트리(octree)로 확장.
복셀(voxel) : 부피가 있는 픽셀(volume pixel). 2차원 픽실에 대응하는 3차원 요소
계산을 회피하는 그 밖의 수학적 기법들
복잡한 회피 기법
- 멱급수 근삿값 계산
테일러 급수(Taylor series) : 사인 함수를 계산하는 다른 방법. 항의 수를 늘리면 테일러 급수가 이상적 사인 함수에 가까워짐.
- CORDIC 알고리즘
컨베어(Convair)의 잭 볼더(Jack Volder). 1956년 좌표 회전 디지털 컴퓨터(CORDIC, Coordinate Rotation Digital Computer) 알고리즘 개발. 폭격기 항법 시스템의 아날로그 부품을 정확하게 대신하기 위해 고안.
삼각함수, 로그함수 계산.
-벡터링모드(vectoring mode) : 다른 버전의 CORDIC 알고리즘
-회전모드(rotation mode) : 좀 더 이해하기 쉬움.
무작위성과 관련 있는 예제들
컴퓨터에서 완전한 난수(임의의 수)를 계산하기는 아주 어렵다. 난수를 만들려면 어떤 공식을 기반으로 생성해야 하는데, 정해진 공식으로 생성한 난수는 반복적일 수 밖에 없다.
의사난수성(pseduorandomness)을 활용한 몇 가지 근삿값 계산 방법.
- 공간을 채우는 곡선
- L 시스템
- 스토캐스틱 기법
- 양자화
12장 병렬성과 비동기성
핸드폰도 멀티프로세서 시스템. 경합 조건(race condition). 일부 연산에 대해서는 근본적으로 멀티태스킹을 막아야 한다. 하지만 멀티태스킹의 이점을 잃지 않고 경함 조건을 해결, 락을 사용하기는 어렵다.
경합 조건이란 무엇인가
프로그램이 자원 사용 순서에 따라 결과가 달라지는 경우. 공유자원(shared resource)에 접근 하는 타이밍에 따라 달라진다.
공유 자원
메모리는 항상 공유 문제와 관련된 경우.
입출력(I/O) 장치 하드웨어 들어있는 어떤 비트일 수도 있다.
프로세스와 스레드
병렬로 실행되는 프로그램이 자원을 공유해야 경합 조건이 발생.
자원을 공유하는 프로세스들은 어떤 방식으로든 서로 통신을 해야 한다.
스레드(thread) : 정적인 데이터와 힙을 공유. 자체적으로 스택을 갖는 프로그램의 일부분 의미.
락
- 트랜잭션과 작업 크기
- 락 대기
- 교착 상태
- 단기 락 구현
- 장기 락 구현
브라우저 자바스크립트
비동기 함수와 프로미스
