Skip to content

Latest commit

 

History

History
68 lines (48 loc) · 5.78 KB

README.md

File metadata and controls

68 lines (48 loc) · 5.78 KB
Raw

Лабораторная работа 1. Динамическая память, адресная арифметика.

При решении задач в методических целях нельзя использовать выражение вида a[i] и 
вообще квадратные скобки (только в этой лабораторной работе). Вместо него используется 
выражение *pa, где pa - указатель на i-ый элемент массива (именно на i-ый элемент, а не 
выражение вида *(pa + i)). Также нельзя передавать как аргумент размер массива в элементах, 
если массив уже создан. Вместо этого предлагается использовать пару указателей: на первый элемент 
массива и на элемент массива, расположенный за последним. Ситуация когда эти массивы совпадают, 
означает пустоту обрабатываемого массива.

🔴 Задача 1

Написать программу, которая считывает из текстового файла целые числа в массив и выполняет обработку этого массива (см. распределение вариантов). Память под массив выделяется динамически. Число элементов в массиве определяется в первом проходе по текстовому файлу, во время второго прохода числа считываются в массив. Имя файла передается через параметры командной строки.

🔷 Варианты

  1. ✅ Вычислить значение max(x[0] + x[n-1], x[1] + x[n-2], x[2] + x[n-3], ..., x[(n-1)/2] + x[n/2]), где n размер массива.
  2. Вычислить значение x[0]*y[0]+x[1]*y[1]+ ... + x[k]*y[k], где x[i] – отрицательные элементы массива a из n элементов, взятые в порядке их следования; y[i] – положительные элементы этого массива, взятые в обратном порядке; k = min(p,q), где p – количество положительных элементов массива a, q – количество отрицательных элементов этого массива.
  3. Вычислить значение x[0] + x[0]*x[1] + x[0]*x[1]*x[2] + ... + x[0]*x[1]*x[2] ... x[m], где x[i] - элементы массива x из n элементов, m - индекс первого отрицательного элемента этого массива либо число n-1, если такого элемента в массиве нет.
  4. Вычислить значение min(x[0]*x[1], x[1]*x[2],x[2]*x[3], ..., x[n-3]*x[n-2], x[n-2]*x[n-1]), где x[i] - элементы массива x из n элементов.
  5. Найти количество различных чисел в файле.

🔴 Замер времени

Практически каждый процессор имеет специальный встроенный регистр - счетчик тактов, значение которого можно получить специальной командой процессора. Команда процессора RDTSC (Read Time Stamp Counter) возвращает в регистрах EDX и EAX 64-разрядное беззнаковое целое, равное числу тактов с момента запуска процессора. Вызвав эту команду до и после участка программы, для которого требуется вычислить время исполнения, можно вычислить разность показаний счетчика. Оно равно числу тактов, затраченных на исполнение замеряемого участка. Для перехода от числа тактов к времени требуется умножить число тактов на время одного такта (величина, обратная тактовой частоте процессора). Для процессора с тактовой частотой 1ГГц время такта - 1 нс.

Достоинством этого способа является максимально возможная точность измерения времени, недостатком - команда получения числа тактов зависит от архитектуры процессора.

Недостатки способа и подходы к борьбе с ними описаны в работе «Использование Time-Stamp Counter для измерения времени выполнения кода на процессорах с архитектурой Intel 64 и IA-32» Михаила Курносова.

#include <stdio.h>

unsigned long long tick(void)
{
    unsigned long long d;

    __asm__ __volatile__ ("rdtsc" : "=A" (d) );

    return d;
}

void test(void)
{
    long double test = 0.0;

    for(unsigned long long i = 0; i < 10000; i++)
        test += 0.5;
}

#define N 5

int main(void)
{
    unsigned long long tb, te;

    tb = tick();
    for(int i = 0; i < N; i++)
        test();
    te = tick();

    printf("test 'time': %llu\n", (te - tb) / N);

    return 0;
}