BG Development


Страници: (3) 1 2 [3]   ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Асемблер задача с масиви, програма на асемблер ,работа с масиви
AK-85
Публикувано на: 08-05-2018, 02:25
Quote Post



Име:
Група: Потребител
Ранг: Старо куче

Мнения: 741
Регистриран на: 06.07.06



QUOTE (40oz @ 02-05-2018, 12:35)
То има цяла книга и курс по въпроса - From And to Tetris icon_smile.gif

Всъщност е "From Nand to Tetris", а идеята беше да се ползва само AND (иначе на всички ни е ясно, че NAND е универсална операция), но както и да е...

Двете задачи всъщност са пример за модела "MapReduce", затова има сравнително естествени паралелни решения, само че в случая не се използва клъстер, а един процесор. На мен ми дойде вдъхновението и разписах неоново, т.е. векторно решение, което приема, че средата поддържа неподравнен достъп до паметта (в противен случай прологът на векторния цикъл ще се усложни):
CODE
      .text
      .align      2
      .global      count
      .type      count, %function
count:
      mov            r12, r0
      lsrs            r3, r1, #4
      mov            r0, #0
      beq            .Lscalar

      and            r1, r1, #15
      vdup.8            q0, r2
      vmov.i64      q1, #0

.Lvector_loop:
      vld1.64            {q2}, [r12]!
      subs            r3, r3, #1
      vceq.i8            q2, q0, q2
      vpaddl.s8      q2, q2
      vpadal.s16      q1, q2
      bne            .Lvector_loop

      vneg.s32      q0, q1
      vpaddl.u32      q0, q0
      vadd.i32      d0, d0, d1
      vmov            r0, s0

.Lscalar:
      cmp            r1, #0
      bxeq            lr

.Lscalar_loop:
      # Fill in 5 instructions.

      bx            lr
      .size      count, .-count

Основният цикъл е unroll-нат, така че да позволи векторизация, но нищо по-сложно. Нарочно махнах скаларния цикъл, защото нямам намерение да решавам домашни, но в темата има достатъчно материал да се попълни. Аспектът "map" се покрива от VCEQ, а "reduce" - от VPADDL + VPADAL.

Кодът отговаря на AAPCS, което означава, че лесно се извиква от C с прототип на функцията от рода на:
CODE
size_t count(const unsigned char *a, size_t n, unsigned char c);

За C++ се добавя "extern "C"" отпред.

Ето примерен тестов код (може да се намали MAX_ARRAY_SIZE за по-бързо изпълнение):
CODE
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET "AbCdE01234?!@$%"
#define MAX_ARRAY_SIZE 65536

size_t count(const unsigned char *a, size_t n, unsigned char c);

static size_t reference_count(const unsigned char *a, size_t n, unsigned char c)
{
      size_t ret = 0;

      for (size_t i = 0; i < n; i++)
            if (a[i] == c)
                  ret++;

      return ret;
}

int main(void)
{
      int ret = EXIT_FAILURE;
      bool error = false;
      unsigned char array[MAX_ARRAY_SIZE];

      memset(array, 0, sizeof(array));

      if (count(NULL, 0, 0)) {
            puts("empty array");
            error = true;
      }

      for (size_t i = 1; i < sizeof(array) - 1; i++) {
            srand(i);

            for (size_t j = 0; j < i; j++)
                  array[j] = ALPHABET[rand() % (sizeof(ALPHABET) - 1)];

            const unsigned char c = ALPHABET[rand() % (sizeof(ALPHABET) - 1)];
            const size_t ref = reference_count(array, i, c);
            const size_t res = count(array, i, c);

            if (ref != res) {
                  printf("%s, %zu, %c, %zu, %zu\n", array, i, c, ref, res);
                  error = true;
            }
      }

      if (!error) {
            puts("No errors.");
            ret = EXIT_SUCCESS;
      }

      return ret;
}


Ако човек има телефон с "Android", има относително лесен начин да се изпълни кодът. Първо телефонът се настройва за разработка, като се следват официалните инструкции (процесът е обратим, а и не променя нещо съществено по системата), а това ръководство описва стъпките за инсталация на toolchain, както и как да се прехвърли и пусне изпълнимият файл на устройството с "adb" ("/data/local/tmp" е удобна директория за временни файлове, защото е достъпна и за непривилегировани потребители).

Ако кодът на C е в "main.c", а асемблерният - в "count.S", компилира се с:
CODE
arm-linux-androideabi-gcc -std=c11 -march=armv8-a -mfpu=neon-fp-armv8 -pie -fpie -o test main.c count.S

И се тества с:
CODE
adb push test /data/local/tmp
adb shell /data/local/tmp/test


Проблемът с телефоните е, че по принцип не са подходящи за получаване на стабилни резултати от microbenchmark-ове, най-вече заради thermal throttling-а, но освен това "Android" се състои от доста процеси, които се състезават за процесорните ядра. Това донякъде се решава с настройки (застопоряване на процесорната честота на определена, сравнително ниска стойност, изолиране на дадено ядро и т.н.), които за съжаление изискват root-нат телефон. Нямам под ръка такъв, затова не мога да направя качествено сравнение на времената за изпълнение, нито да правя по-сложни оптимизации като агресивен loop unrolling и software pipelining (което е безсмислено без идея за времето за изпълнение, защото лесно може да доведе до по-лоши резултати).
PM
Top
Дон Реба
Публикувано на: 08-05-2018, 05:59
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 6546
Регистриран на: 11.11.06



престараваш се, мен ми изглежда че въпроса е за курсова работа
PM
Top
Дон Реба
Публикувано на: 08-05-2018, 06:02
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 6546
Регистриран на: 11.11.06



между другото, като заговорихме за универсални базиси, навремето преди интернета, даскала ни каза че с ла3ка можело да се направи ксор и ни остави за домашно да помислим как. никой не успя да го измисли, интересно ми е някой изобщо успявал ли е без гугъл
PM
Top
Gamma Goblin
Публикувано на: 08-05-2018, 08:19
Quote Post



Име: Кратос
Група: Потребител
Ранг: Старо куче

Мнения: 626
Регистриран на: 21.02.18



QUOTE
ла3ка
?


--------------------
Напред! Живота е сраженье!
Напред! И прав всегда ходи!
Напред, макар към поражение!
Ако ще паднеш, прав падни!
---
Axis of faith; Raw, and untamed in spirit
To do and undo...
We chew this world; And Spit it out
PMEmail Poster
Top
Дон Реба
Публикувано на: 08-05-2018, 08:39
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 6546
Регистриран на: 11.11.06



7400
PM
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (3) 1 2 [3]  Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2018 | BG Development | All Rights Reserved
RSS 2.0