Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
#1

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

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

Пусть заданы две квадратных матрицы 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 такта), реальное время вычисления.

Кто свободен, может поможите?.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2011, 15:52     Немного из архитектуры ЭВМ
Посмотрите здесь:

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

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

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

Организация архитектуры движка - C++
коротко интро: Есть три компонента, они в исходниках естессно, так как пишу их я. так вот эти три компонента должны ...

Задача проектирования архитектуры - C++
добрый день. недавно дали первое моё самостоятельное задание. ну, как самостоятельное, просто мне дали в этом задании полную свободу...

Предложения по изменению архитектуры - C++
Есть код (много но просто): #include &lt;iostream&gt; #include &lt;memory&gt; #include &lt;vector&gt; using namespace std; class SceneNode ...

Ошибка при построении архитектуры if-else - C++
Добрый день! Написал программу по условию: (см. 1 картинку) Выглядит программа так: #include &quot;stdio.h&quot; #include...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
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 арифм операции.
Во-втором одно обращение и две операции
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 16:36  [ТС]     Немного из архитектуры ЭВМ #3
А как вычислить реальное время вычисления?
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
29.04.2011, 16:47     Немного из архитектуры ЭВМ #4
Если в ваших тактах, то умножьте число действий на длительность действия в тактах. А рельное никак, оно завист от кучи параметров.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 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 большое, то разница будет минимальна или её не будет вообще
это осталось истинным.)
А считать такты это жжжесть!
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:04  [ТС]     Немного из архитектуры ЭВМ #6
Спасибо.. а сравнить время вычислений может возможно при помощи каких-нибудь функций?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:06     Немного из архитектуры ЭВМ #7
GetTickCount() до и после. Разница между ними будет временем.

Но время выполнения должно быть больше 1 тысячной секунды.
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:11  [ТС]     Немного из архитектуры ЭВМ #8
Можете помочь с кодом программы с использованием функции?
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
29.04.2011, 18:14     Немного из архитектуры ЭВМ #9
Deviaphan, чет вы мне все предстваление о мире сломали. Делаю тест, первый вариант быстрее выходит... умя ступор
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:17     Немного из архитектуры ЭВМ #10
Цитата Сообщение от KuKu Посмотреть сообщение
умя ступор
Во первых, тестируй в релизе. Во вторых, большое N - это хотя бы несколько тысяч.
oksanaBM
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();
}


чем она мне помочь может... наверно ничем. не знаю...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:19     Немного из архитектуры ЭВМ #12
QueryPerformanceCounter точнее, чем GetTickCount, но N слишком маленькое.
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:20  [ТС]     Немного из архитектуры ЭВМ #13
не. я тупанула..
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
29.04.2011, 18:21     Немного из архитектуры ЭВМ #14
Цитата Сообщение от Deviaphan Посмотреть сообщение
Во первых, тестируй в релизе. Во вторых, большое N - это хотя бы несколько тысяч.
Массив 5000*5000 и 25000000. Постоянно на процентов 10 медленее.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:28     Немного из архитектуры ЭВМ #15
i,j разные пробовал или в конце массива?
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
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");
}
Может туплю в чем-то.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
29.04.2011, 18:32     Немного из архитектуры ЭВМ #17
Т.е. в строке 20 время больше, чем в строке 25?
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
29.04.2011, 18:33     Немного из архитектуры ЭВМ #18
Да,
12979 и 7427
oksanaBM
1 / 1 / 0
Регистрация: 27.01.2011
Сообщений: 91
29.04.2011, 18:47  [ТС]     Немного из архитектуры ЭВМ #19
У меня этот код не работает . . пишет "не разрешенная функция timeGetTime".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2011, 18:48     Немного из архитектуры ЭВМ
Еще ссылки по теме:

Программа проверки знания истории архитектуры - C++
Напишите программу проверки знания истории архитектуры. Программа должна вывести вопрос и три варианта ответа. Пользователь должен выбрать...

Нужна помощь в выборе архитектуры системы. - C++
Стоит задача создать довольно сложную систему. Прошу помоч в выборе архетектуры. Примерное ТЗ: Есть много (150-200) компьютеров,...

Эмуляция х86 архитектуры для работы borland 3.1 - C++
Тема в сабже, собственно. Подскажите хороший эмулятор. DosBox - не совсем устраивает. слишком много багов. либо посоветуйте...

Посоветуйте литературу или статьи по правильному составлению архитектуры кода программ - C++
Здравствуйте программисты. Посоветуйте пожалуйста литературу или статьи по правильному составлению архитектуры кода программ. А то...

Архитектура ЭВМ на С++ - C++
1. Определить режимы работы каналов таймера. 2. Реализовать программу генерации звука с определением частоты звучания случайным...


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

Или воспользуйтесь поиском по форуму:
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
29.04.2011, 18:48     Немного из архитектуры ЭВМ #20
либу надо подключить.
Yandex
Объявления
29.04.2011, 18:48     Немного из архитектуры ЭВМ
Закрытая тема Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru