АОР2/Јул 2022 - Историја измена

KockaAdmiralac: /* Решење */ Šta

2023-06-05T13:29:15Z

Решење: Šta

← Старија измена		Верзија на датум 5. јун 2023. у 15:29
Ред 297:		Ред 297:
	LD R16, (R18)adr		LD R16, (R18)adr
	ANDI R19, R17, #4		ANDI R19, R17, #4
	LD R16, (R16)~~0XOR~~		LD R16, (R16)0
	LSRI R19, R19, #2		LSRI R19, R19, #2
	ADD R16, R16, R19		ADD R16, R16, R19

KockaAdmiralac: /* Решење */ Ispravka registra koji se koristi kao SP

2023-06-05T13:26:14Z

Решење: Ispravka registra koji se koristi kao SP

← Старија измена		Верзија на датум 5. јун 2023. у 15:26
Ред 256:		Ред 256:
	\|		\|
	LD R16, (R13)-1		LD R16, (R13)-1
	ADDI ~~R16~~, ~~R16~~, #-1		ADDI R13, R13, #-1
	BEQZ R18, (R18+R16)		BEQZ R18, (R18+R16)
	\| У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R18 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC.		\| У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R18 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC, па стога и специфичан начин обележавања (који је еквивалентан са <code>(R16)0</code>).
	\|-		\|-
	\| <code>SUB (adr)</code>		\| <code>SUB (adr)</code>

KockaAdmiralac: /* Решење */ Nepotreban ANDI u ADDB

2023-06-05T13:04:26Z

Решење: Nepotreban ANDI u ADDB

← Старија измена		Верзија на датум 5. јун 2023. у 15:04
Ред 229:		Ред 229:
	AX<sub>7..0</sub> = AX<sub>7..0</sub> + Rx<sub>7..0</sub>		AX<sub>7..0</sub> = AX<sub>7..0</sub> + Rx<sub>7..0</sub>
	\|		\|
	~~ANDI R16, Rx, #00FF~~		ADD R0, R0, Rx
	ADD R0, R0, ~~R16~~
	ANDIS R0, R0, #00FF		ANDIS R0, R0, #00FF
	\| Трећа инструкција ажурира PSW како би поставила N и Z битове.		\| Трећа инструкција ажурира PSW како би поставила N и Z битове.

KockaAdmiralac: Rešeno // Edit via Wikitext Extension for VSCode

2023-05-25T21:31:18Z

Rešeno // Edit via Wikitext Extension for VSCode

Прикажи измене

KockaAdmiralac: Rešenje drugog zadatka

2023-05-24T22:13:11Z

Rešenje drugog zadatka

← Старија измена		Верзија на датум 25. мај 2023. у 00:13
Ред 28:		Ред 28:

	=== Решење ===		=== Решење ===
			Испод је дата тражена имплементација функције као и остатак програма који тестира перформансе и успешност ове реимплементације:
			<syntaxhighlight lang="cpp">
			#include <chrono>
			#include <cstdlib>
			#include <iostream>
			#include <immintrin.h>

			const int N = 65530;
			const int MIN = 0;
			const int MAX = RAND_MAX / 10;

			// Унија за приступ појединачним члановима вектора.
			union V256I {
			__m256i v;
			int i[8];
			};

			// Низови за податке који се прослеђују функцијама.
			unsigned int niz1[N];
			unsigned int niz2[N];

			// Оригинални код из задатка.
			int elementsInRangeOriginal(const unsigned int* input, unsigned int n, unsigned int min, unsigned int max) {
			int result = 0;

			for (unsigned int i = 0; i < n; i++) {
			if (input[i] >= min && input[i] <= max)
			result = result + 1;
			}

			return result;
			}

			// SIMD-оптимизован код.
			int elementsInRangeSIMD(const unsigned int* input, unsigned int n, unsigned int min, unsigned int max) {
			unsigned int roundedDownN = (n / 8) * 8;
			// Сви вектори потребни за рад функције.
			V256I resultVector;
			resultVector.v = _mm256_set_epi32(0, 0, 0, 0, 0, 0, 0, 0);
			__m256i minVector = _mm256_set_epi32(min, min, min, min, min, min, min, min);
			__m256i maxVector = _mm256_set_epi32(max, max, max, max, max, max, max, max);
			__m256i zeroVector = _mm256_set_epi32(0, 0, 0, 0, 0, 0, 0, 0);
			for (unsigned int i = 0; i < n; i += 8) {
			__m256i inputVector = _mm256_loadu_si256((__m256i*)(input + i));
			// _mm256_cmpgt_epi32 ће поставити све јединице на места где је испуњен
			// услов.
			__m256i minCompareVector = _mm256_cmpgt_epi32(inputVector, minVector);
			__m256i maxCompareVector = _mm256_cmpgt_epi32(maxVector, inputVector);
			// Остављамо све јединице на месту где су испуњена оба услова, и за
			// минимум и за максимум.
			__m256i blendedVector = _mm256_blendv_epi8(zeroVector, maxCompareVector, minCompareVector);
			// Напомена: све јединице заправо означавају број -1, па у овом вектору
			// чувамо негативне бројаче уместо позитивне.
			resultVector.v = _mm256_add_epi32(resultVector.v, blendedVector);
			}
			int result = 0;
			for (unsigned int i = 0; i < 8; ++i) {
			// Пошто смо изнад додавали негативне бројеве на резултат, овде морамо
			// да обрнемо знак да бисмо израчунали крајњи резултат како треба.
			result -= resultVector.i[i];
			}
			// Урачунавамо све преостале елементе у резултат.
			for (unsigned int i = roundedDownN; i < n; ++i) {
			if (input[i] >= min && input[i] <= max) {
			++result;
			}
			}
			return result;
			}

			int main() {
			// Пунимо улазне низове насумичним подацима.
			for (int i = 0; i < N; ++i) {
			unsigned int randomNumber = static_cast<unsigned int>(rand());
			niz1[i] = randomNumber;
			niz2[i] = randomNumber;
			}
			// Меримо време колико је потребно оригиналном коду да се изврши.
			std::chrono::steady_clock::time_point beginOriginal = std::chrono::steady_clock::now();
			int resultOriginal = elementsInRangeOriginal(niz1, N, MIN, MAX);
			std::chrono::steady_clock::time_point endOriginal = std::chrono::steady_clock::now();
			std::cout << "Original: " << std::chrono::duration_cast<std::chrono::microseconds>(endOriginal - beginOriginal).count() << "ms" << std::endl;
			// Меримо време колико је потребно SIMD коду да се изврши.
			std::chrono::steady_clock::time_point beginSIMD = std::chrono::steady_clock::now();
			int resultSIMD = elementsInRangeSIMD(niz2, N, MIN, MAX);
			std::chrono::steady_clock::time_point endSIMD = std::chrono::steady_clock::now();
			std::cout << "SIMD: " << std::chrono::duration_cast<std::chrono::microseconds>(endSIMD - beginSIMD).count() << "ms" << std::endl;
			// Упоређујемо резултате оригиналног и SIMD кода.
			if (resultOriginal != resultSIMD) {
			std::cerr << "Result mismatch (original: " << resultOriginal << ", SIMD: " << resultSIMD << ")" << std::endl;
			return EXIT_FAILURE;
			}
			return EXIT_SUCCESS;
			}
			</syntaxhighlight>
			Решење превести коришћењем команде <code>g++ -march=native fajl.cpp</code>.

	== 3. задатак ==		== 3. задатак ==

KockaAdmiralac: Julski rok prošle godine // Edit via Wikitext Extension for VSCode

2023-05-22T17:42:33Z

Julski rok prošle godine // Edit via Wikitext Extension for VSCode

Нова страница

{{tocright}}
{{нерешено}}
'''Јулски рок 2022. године''' одржан је 2. јула и трајао је 90 минута. На испиту је такође био подељен [[#Подсетник|подсетник векторских инструкција са документацијом AVX инструкција са Интеловог званичног сајта]].

== 1. задатак ==
=== Поставка ===
Описати технику оптимизације векторских инструкција која се заснива на дохватању изабраних елемената ('''''Scatter-gather''''') приликом приступа подацима. Дати пример инструкција процесора које омогућавају ову технику и пример програма код кога се јасно види предност коришћења ове технике.

=== Решење ===

== 2. задатак ==
=== Поставка ===
Дата је функција <syntaxhighlight lang="c" inline>int elementsInRange(const unsigned int* input, int n, int min, int max)</syntaxhighlight> која за целобројне елементе низа задатог показивачем <code>input</code> и дужине <code>n</code> пребројава колико има елемената у интервалу <code>[min, max]</code>. Сматрати да је n > 0. Елементи низа су цели бројеви <code>int</code> (32 bit).

Потребно је преправити код тако да има исти резултат извршавања коришћењем векторских инструкција које су дате у прилогу испита.
<syntaxhighlight lang="c">
int elementsInRange(const unsigned int* input, int n, int min, int max) {
int result = 0;

for (int i = 0; i < n; i++) {
if (input[i] >= min && input[i] <= max)
result = result + 1;
}

return result;
}
</syntaxhighlight>

=== Решење ===

== 3. задатак ==
=== Поставка ===
Описати технику коришћења кеша за чување трагова извршавања ('''''Trace cache'''''). Дати пример места у проточној обради где се овај кеш може налазити и образложити одговор. Шта представљају улази и излази и описати по чему се овај кеш разликује од обичне кеш меморије.

=== Решење ===

== 4. задатак ==
=== Поставка ===
Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 4.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (''Instruction PreDecode'') који[sic] обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра[sic] опште намене. Адресе и подаци су величине 16 бита.
[[Датотека:AOR2 organizacija PreDecode.svg|thumb|center|500px|Слика 4.1. — организација процесора]]
<div class="abc-list">
# Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 4.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор. Бит PSWI у PSW се налази на позицији 3, бит PSWC у PSW се налази на позицији 2. У табели 4.1. акције нису оптимизовано написане, већ описно.
# Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 4.1.).
</div>
{| class="wikitable"
|+ Табела 4.1. — део инструкцијског сета процесора
! Асемблерска инструкција
! Акција
! Микро инструкције
|-
| <code>ADDB Rx</code>
|
AX15..8 = 0
AX7..0 = AX7..0 + Rx7..0
|
|-
| <code>ENTER immed</code>
| <pre>
PUSH BP
BP = SP
SP = SP + immed
</pre>
|
|-
| <code>INTD</code>
| <code>PSWI = 0</code>
|
|-
| <code>POPPC</code>
| <code>POP PC</code>
|
|-
| <code>SUB (adr)</code>
| <code>AX = AX - MEM[MEM[adr]]</code>
|
|-
| <code>LOOPZ disp</code>
| <pre>
R12 = R12 - 1
IF R12 == 0 THEN
PC = PC + disp
</pre>
|
|-
| <code>LD +(Rx)</code>
| <pre>
Rx = Rx - 1
ACC = MEM[Rx]
</pre>
|
|-
| <code>SUBC (adr)</code>
| <pre>
IF PSWC == 1 THEN
ACC = ACC - MEM[MEM[adr]] - 1
ELSE
ACC = ACC - MEM[MEM[adr]]
</pre>
|}

=== Решење ===

== Подсетник ==
У подсетнику је била дата документација за следеће инструкције:
* <code>_mm256_loadu_si256</code>
* <code>_mm256_set_epi32</code>
* <code>_mm256_cmpgt_epi32</code>
* <code>_mm256_mul_epi32</code>
* <code>_mm256_storeu_epi32</code>
* <code>_mm256_blendv_epi32</code>
* <code>_mm256_add_epi32</code>
Документација за ове инструкције може се наћи са [https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html званичног Интеловог сајта] и овде неће бити поновљена.

[[Категорија:Рокови]]
[[Категорија:АОР2]]