1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
1

Немного из архитектуры ЭВМ

29.04.2011, 15:52. Показов 2519. Ответов 30
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Пусть заданы две квадратных матрицы A и B размером NxN.
Они созданы с помощью двух подходов:

1 подход:
C++
1
2
3
4
int **A;
A = new int*[N];
for(int i=0;i<N;i++)
A[i] = new int[N];
Доступ к элементу: A[i][j]

2 подход:
C++
1
2
int *A;
A = new int[N*N];
Доступ к элементу: A[i*N+j]

Необходимо сложить эти матрицы и сравнить время вычисления. Нужны выводы по этим подходам: количество обращений к памяти,
вычислений, теоретические оценки времени вычислений (можно считать, что
матрицы не загружаются в кэш, время доступа к одному элементу в памяти 10
тактов, арифметическая операция 2 такта), реальное время вычисления.

Кто свободен, может поможите?.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.04.2011, 15:52
Ответы с готовыми решениями:

Из архитектуры ЭВМ
Здравствуйте! Хотел бы попросить помочь вот с каким вопросом: описать механизм выбора банков...

Первая ЭВМ сеть, то есть первое соединение ЭВМ было электротехническим (радиотехническим) или электронным?
Первая ЭВМ сеть, то есть первое соединение ЭВМ было электротехническим (радиотехническим) или...

Структура "ЭВМ". Определить какая ЭВМ имеет минимальное отношение стоимость/быстродействие
Даны 3 ЭВМ , известны объемы памяти, цена и быстродействие. Определить какая ЭВМ имеет минимальное...

В наушник попало немного воды и он стал немного тише играть
В наушник попало немного воды и он стал немного тише играть. Это практически не заметно, но всё же...

30
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 16:18 2
A[j][i] => A[j] + i*sizeof(int*) =>A + sizeof(int)*j + i*sizeof(int*)
A[i] => A+i*sizeof(int)

По идее в первом подходе на одно считывание элемента приходится два обращения к памяти и 4 арифм операции.
Во-втором одно обращение и две операции
1
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 16:36  [ТС] 3
А как вычислить реальное время вычисления?
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 16:47 4
Если в ваших тактах, то умножьте число действий на длительность действия в тактах. А рельное никак, оно завист от кучи параметров.
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:03 5
С некоторой долей уверенности можно утверждать, что второй вариант будет быстрее при малых размерах N (т.е. когда весь массив помещается в одной странице). Если N большое, то разница будет минимальна или её не будет вообще.
A[i][j] и A[i*N+j] равнозначны, т.к. любой вменяемый компилятор сгенерирует для них одинаковый код.

Добавлено через 6 минут
Цитата Сообщение от Deviaphan Посмотреть сообщение
A[i][j] и A[i*N+j] равнозначны, т.к. любой вменяемый компилятор сгенерирует для них одинаковый код.
А я соврал.) Это только для статически создаваемых массивов.)

Добавлено через 51 секунду
Однако,
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если N большое, то разница будет минимальна или её не будет вообще
это осталось истинным.)
А считать такты это жжжесть!
1
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:04  [ТС] 6
Спасибо.. а сравнить время вычислений может возможно при помощи каких-нибудь функций?
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:06 7
GetTickCount() до и после. Разница между ними будет временем.

Но время выполнения должно быть больше 1 тысячной секунды.
0
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:11  [ТС] 8
Можете помочь с кодом программы с использованием функции?
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 18:14 9
Deviaphan, чет вы мне все предстваление о мире сломали. Делаю тест, первый вариант быстрее выходит... умя ступор
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:17 10
Цитата Сообщение от KuKu Посмотреть сообщение
умя ступор
Во первых, тестируй в релизе. Во вторых, большое N - это хотя бы несколько тысяч.
0
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:17  [ТС] 11
)))) блин а у меня зачет ломается)) я сделала только вот эту прогу -
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdafx.h>
#include <windows.h>
#include <ctime>
#include <conio.h>
#include <locale.h>
 
#define N 200
 
void main()
{setlocale(LC_CTYPE, "Russian");
LARGE_INTEGER b_start,b_stop,freq;
QueryPerformanceFrequency(&freq);
long long int a[N][N], b[N][N], c[N][N];
srand(time(NULL));
int i,j,k;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
{     a[i][j] = rand()%N;
     b[i][j] = rand()%N;        }
QueryPerformanceCounter(&b_start);
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
for(k = 0; k < N; k++)
       c[i][j] += a[i][k] + b[k][j];
QueryPerformanceCounter(&b_stop);
printf("Время стандартного алгоритма: %lf мксек\n", (double)(b_stop.QuadPart - b_start.QuadPart)*1000000.0/(double)(freq.QuadPart));
QueryPerformanceCounter(&b_start);
for(i = 0; i < N; i++)
for(k = 0; k < N; k++)
for(j = 0; j < N; j++)
       c[i][j] += a[i][k] + b[k][j];
QueryPerformanceCounter(&b_stop);
printf("Время алгоритма с учетом прямого обхода памяти: %lf мксек\n", (double)(b_stop.QuadPart - b_start.QuadPart)*1000000.0/(double)(freq.QuadPart));
_getch();
}


чем она мне помочь может... наверно ничем. не знаю...
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:19 12
QueryPerformanceCounter точнее, чем GetTickCount, но N слишком маленькое.
0
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:20  [ТС] 13
не. я тупанула..
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 18:21 14
Цитата Сообщение от Deviaphan Посмотреть сообщение
Во первых, тестируй в релизе. Во вторых, большое N - это хотя бы несколько тысяч.
Массив 5000*5000 и 25000000. Постоянно на процентов 10 медленее.
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:28 15
i,j разные пробовал или в конце массива?
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 18:30 16
Для массива 7000*7000, вообще в полтора-два раза медленнее.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
i,j разные пробовал или в конце массива?
Не понял.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include "windows.h"
 
using namespace std;
int main()
{
 
    int** a;
    int size = 7000;
    a=new int*[size];
    for(int i=0;i<size;++i) a[i]=new int[size];
    
    int* b;
    b=new int[size * size];
    int timer;
    
    timer = timeGetTime();    
    for(int i=0;i<size*size;++i) b[i] = 10;
    cout << timeGetTime() - timer << endl; 
        
    timer = timeGetTime();
    for(int i=0;i<size;++i)
        for(int j=0;j<size;++j) a[i][j] = 10;
    cout << timeGetTime() - timer << endl; 
  
    system("pause");
}
Может туплю в чем-то.
1
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:32 17
Т.е. в строке 20 время больше, чем в строке 25?
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 18:33 18
Да,
12979 и 7427
0
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:47  [ТС] 19
У меня этот код не работает . . пишет "не разрешенная функция timeGetTime".
0
1563 / 1041 / 94
Регистрация: 17.04.2009
Сообщений: 2,995
29.04.2011, 18:48 20
либу надо подключить.
0
29.04.2011, 18:48
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.04.2011, 18:48
Помогаю со студенческими работами здесь

Статья 1280. Свободное воспроизведение программ для ЭВМ и баз данных. Декомпилирование программ для ЭВМ
И так уважаемая Администрация. Я вам могу сказать: Обсуждение реверса не является незаконным ;) ...

Проектирование ОО архитектуры
Интересно мнение публики. &quot;Программирование в терминах интерфейсов&quot; Вопрос такой: как правильно...

Архитектуры процессоров
Здравствуйте, у меня есть один вопрос. Есть такие архитектуры, как CISC, RISC, MISC, VLIW etc. И...

Реализация архитектуры
Задача такая. Есть класс строк ( десятичная , символьная и т.п.) и операции к ним. Я собрал...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Закрытая тема Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru