VPF::Мнопоточный итерационный алгоритм

x8m6

Дата 11.12.2008, 14:43 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 156
Регистрация: 11.12.2008

Репутация: нет
Всего: нет

В общем есть один итерационный метод , с помощью которого решаются системы линейных алгебраических уравнений. Этот метод называется методом сопряженных градиентов (может кто слышал).
Чтобы было понятно приведу сразу его код (последовательный алгоритм):
Класс самого метода

Код


class Conjugate_Gradient {
         
         
      private double[][] A; // квадратная вещественная матрица, размера [n x n]                 
      private double[] b;  //  вектор правых частей, разиера n;   
      double[] x; // вектор решений, размера n;
      private double eps; // точность     
     
      private int iter; // количество итераций метода;
      private int n;    // размерность системы
                 
      private double [] r;  //Вектор невязки
      private double [] z;  //Вектор градиентного спуска
      private double [] q;  //Вектор, равный произведению A*z   
      private double [] p; // Вспомогательный вектор
        
       /**
        * Конструктор
        * @param A  квадратная матрица n x n
        * @param b  вектор правых частей
        * @ eps - точночть
         */ 
        public Conjugate_Gradient(double[][] A , double[] b, double eps){
           
           this.A = A;
           this.b = b;
           this.eps = eps;
           n = b.length;
           iter = 0;
           
           x = new double[n];
           r = new double[n];
           z = new double[n];
           q = new double[n];
           p = new double[n];
           
        }
                                  
    /**
     * Решение системы линейных алгебраических уравнений A*x = b
     * Методом сопряженных градиентов 
     * @return  b - вектор решений
     */
    double[] CG( ){
       
        
   // инициализация переменных
      int i; 
      double alpha,beta,normb,normr,spl,sp1,sp2,sp;       
      alpha = beta = normb = normr  =  sp1 = sp2 = sp  = spl = 0.0;
     
     
   // 1 шаг: выбрать начальное приближение x(0)   
   // 2 шаг: вычислить вектор невязки r(0) = b;
   // 3 шаг: вычислить вектор направлений градиентного спуска z = r(0)
     
     
      for (i=0;i<n;i++){
          x[i] = 0.0;
          r[i] = b[i];
          z[i] = b[i];
         
      }
       
     // вычиляем норму вектора решений
     
      spl = MatrixVectorOperations.scalarVectorsProduct(0, n, b, b);
      normb = Math.sqrt(spl);
     
     
     
 // Главный цикл метода
     
    // iter = 1,2,3....
     
      do {
                 
   iter++;     
         
         
   // 4 шаг: вычислить коэффициент условного минимума alfa = (z,r)/(z,A*z)
   
    // sp1 = (z,r)   
    // q = A*z       
    // sp2 = (z,q)   
    // alfa = sp1/sp2;
         
       
       sp1 = MatrixVectorOperations.scalarVectorsProduct(0, n, z, r);
       q = MatrixVectorOperations.computeMatrixVectorProduct(0, n, A, z, q);       
       sp2 = MatrixVectorOperations.scalarVectorsProduct(0, n, z, q);
       alpha = sp1/sp2;
                       
       
   // 5 шаг: уточнить решение x = x + alpha*z
       
       x = MatrixVectorOperations.saxpy(0, n, x, z, x, alpha, '+');
       
   
       
   // 6 шаг: вычислить новый вектор невязок r = r - alpha*q
       
       r = MatrixVectorOperations.saxpy(0, n, r, q, r, alpha, '-');
             
       
   // 7 шаг: проверить условие выхода |b|<=|r|*eps
       
       
       sp = MatrixVectorOperations.scalarVectorsProduct(0, n, r, r);       
       
       
       normr = Math.sqrt(sp);
       
       if (normr<=normb*eps) break;
       
  // 8 шаг: вычислить вектор нового направления спуска z = r + beta*z;
       
       // beta = (r,r))/(r,r)(iter-1)
       
       beta = sp/spl;
             
       
       spl = sp;
       z = MatrixVectorOperations.saxpy(0, n, r, z, z,beta ,'+');
       
   // перейти на шаг 4:       
         
      } while(true);
             
      return x; 
       
    }

int getIter(){
       return iter;
   }


}

И класс матрично - векторных операций, без которых не обойтись

Код


/**
  * Матрично - векторные операции
  * @author Vitaly
  */
 class MatrixVectorOperations {
     
      /**
     * Скалярное произведение двух векторов res = a*b
     * @param beg  начало цикла
     * @param end  конец цикла
     * @param a  1-ый вектор, размера n
     * @param b  2-ой вектор, размера n
     * @return res - результат скалярного произведения двух векторов
     */
     static double scalarVectorsProduct(int beg,int end, double[] a, double[] b){
         
       double res = 0.0; 
       for (int i = beg;i<end;i++) res+=a[i]*b[i];
       return res;
     }
     
     /**
      * Операция вида z = y 'ch' koef*x
      * @param beg  начало цикла
      * @param end  конец цикла
      * @param y  вектор, размера n
      * @param x  вектор, размера n
      * @param z  вектор, размера n
      * @param  koef  коэффициент умножения
      * @param c  '+'  - сложение, '-' вычитание
      * @return z  результат операции
      */
     
     static double[] saxpy(int beg, int end, double[] y, double[] x, double[] z, double koef, char c ){
       
         if (c == '+')             
             for (int i = beg; i < end; i++) z[i] = y[i] + koef * x[i];
         
         else 
             
             if (c == '-') for (int i = beg; i < end; i++) z[i] = y[i] - koef * x[i];
             else  System.out.println(" Неправильно введен символ ");
         
         return z;
     }
     
     /**
      * Умножение матрицы на вектор c = A*b
      * @param beg начало цикла
      * @param end конец цикла
      * @param A  квадратная матрица, размера [n x n]
      * @param b  вектор на который умножается матрица, размера n
      * @param c  вектор, размера n
      * @return c результат умножения матрицы на вектор
      */
     static double[] computeMatrixVectorProduct(int beg, int end, double[][] A, double[] b, double[] c){
         
         for (int i = beg; i < end; i++) {
             c[i] = 0.0;
             for (int j = 0; j < b.length; j++) {                                     
                     c[i] += A[i][j] * b[j];                 
             }
         }
                         
         return c;
     }
     
              
     /**
      * Вычисление Евклидовой нормы вектора n = ||a||2
      * @param beg начало цикла
      * @param end конец цикла
      * @param a  вектор, размера n
      * @return norm норма вектора
      */
     static double computeVectorNorm(int beg, int end, double[] a){
         
         double norm = 0.0;         
         norm = Math.sqrt(scalarVectorsProduct(beg, end, a, a));               
         return norm;
         
     }
             
 }

Вообщем как он работает вкратце:
Есть матрица A , вектор b и нужно решить систему A*x = b. Т.е. найти
вектор x. Вектор x находится последовательными приближениями. В начальном (нулевом) приближении x - нулевой.
Основной цикл алгоритма (шаг 4 - шаг 8)
И каждый раз на каждой итерации x уточняется, пока не придет к искомому результату. Точность проверяется по невязке (см. шаг 7) и параметру eps .

Метод строит последовательность направлений спуска (вектор z ). Находится коэффициент alpha и по этому коэффициенту уточняется решение (вектор x). Если решение в этом случае не достигло заданной точности, то направления подправляются коэффициентом beta и процедура повторяется.

Пример :

Код


public class Main {

    /**
     *
     */
    public static void main(String[] args) {
        // TODO code application logic here
       
    int  n = 1000;
       
        double[][] A = new double[n][n]     
        double[] b = new double[n];
        double[] x;

        for (int i = 0;i<n;i++) {

      b[i] = i; 

     
        for (int j = 0; j<n;j++) {

       A[i][j] = A[j][i] = i+j;

        }
     
       A[i][i] = 100.0;

        }
         
      double eps = 1e-8;
       
      Conjugate_Gradient cg = new Conjugate_Gradient(A, b, eps);
      x = cg.CG();

        System.out.println("Количество итераций = " + cg.getIter());
       
       // for (int i = 0;i<n;i++) System.out.println("x[ "+i+" ]= "+x[i]);
                   
    }

При n = 100 метод решает за 176 итераций. (20 секунд по времени)

Добавлено @ 14:45
Теперь нужно реализовать всё это в многопоточном виде.

Основными операциями метода (в главном цикле) являются :

1. Умножение матрицы на вектор ( 1 раз);
2. Скалярное произведение векторов (3 раза);
3. Умножение вектора на число и сложение его с другим вектором (операция saxpy) (3 раза)

Чтобы создать многопоточную версию метода нужно лишь их реализовать в параллельном виде. Благо данные операции очень легко поддаются распараллеливанию.
Например нужно умножить матрицу на вектор в параллельном виде.
Каждый поток обрабатывает свою часть матрицы (количество строк) и вектора (элементов). Матрица разбивается на полоски.
Делается это построчно. Это так называемый ленточный подход.

user posted image

Допустим есть матрица 10x10 и 2 потока. В этом случае 1-ый поток обрабатывает с 1 по 5 -ую строчку матрицы. 2-ой поток с 6-ой по 10-ую.

Именно поэтому в классе MatrixVectorOperations все методы имеют два входных параметра begin и end. Чтобы каждый поток мог вызвать метод и указать ему какую часть матрицы (и/или вектора) обрабатывать.

Ну а теперь то, зачем собственно и была создана эта тема и было приведено выше описание - многопоточная версия алгоритма.

Код


class MultiThreadedConjugateGradient {
         
         
      private double[][] A; // квадратная вещественная матрица, размера [n x n]                 
      private double[] b;  //  вектор правых частей, разиера n;   
      double[] x; // вектор решений, размера n;
      private double eps; // точность
     
     
      private int iter; // количество итераций метода;
      private int n;    // размерность системы
         
         
      private double [] r;  //Вектор невязки
      private double [] z;  //Вектор градиентного спуска
      private double [] q;  //Вектор, равный произведению A*z   
      private double [] p; // Вспомогательный вектор

      private int threadsCount; // количество потоков   
   
      private MyThread[] ts; // массив потоков

 public MultiThreadedConjugateGradient(double[][] A , double[] b, double eps, int ThreadsCount){

          this.A = A;
           this.b = b;
           this.eps = eps;
           n = b.length;
           iter = 0;
           
           x = new double[n];
           r = new double[n];
           z = new double[n];
           q = new double[n];
           p = new double[n];
           
           this.threadsCount = ThreadsCount;
           ts = new MyThread[ThreadsCount];

}

double[]  MultiThreadedCG(){
       
         
       // инициализация переменных
      int i; 
      double alpha,beta,normb,normr,spl,sp1,sp2,sp;       
      alpha = beta = normb = normr  =  sp1 = sp2 = sp  = spl = 0.0;
     
     
      int beg = 0;
      int mid = n/threadsCount;
                     
     int parity = mid & 1;
     int ost = 0;   
     
     if (parity!=0)  ost = n - mid*threadsCount;
     
     int end = mid+ost;
         
      for (i=0;i<threadsCount;i++) {
       
       // создаем поток   
          ts[i] = new MyThread(beg, end);
         
      // стартуем поток   
                     
          ts[i].start();
         
       // каждый поток обрабатывает свою часть данных (отпределенное кол-во строк матриц и векторов)
       // beg - начальная строка ; end - конечная   
          beg = end;
          end +=mid;
      }
         
       sleep(100);   
          
   // 1 шаг: выбрать начальное приближение x(0)   
   // 2 шаг: вычислить вектор невязки r(0) = b;
   // 3 шаг: вычислить вектор направлений градиентного спуска z = r(0)
     
     
      for (i=0;i<n;i++){
          x[i] = 0.0;
          r[i] = b[i];
          z[i] = b[i];
         
      }
       
     // вычиляем норму вектора решений
     
      spl = MatrixVectorOperations.scalarVectorsProduct(0, n, b, b);
      normb = Math.sqrt(spl);
     
          
 // Главный цикл метода
     
    // iter = 1,2,3....
     
      do {
                   
            iter++;
           
         //   System.out.println("Итерация "+ iter);
           
         
        // sp1 = (z,r)
           
            sp1 = multithreadedScalarVectorProduct(z, r);
                       
           
        // q = A*z
           
            q = multithreadedMatrixVectorProduct(A, z, q);
           
        // sp2 = (z,q)
           
            sp2 = multithreadedScalarVectorProduct(z, q);
                       
           
            alpha = sp1/sp2;
                       
       
        // x = x + alpha*z
       
             x = multithreadedSaxpy(x, z, x, alpha, '+');
                       
       
        //  r = r - alpha*q
       
             r = multithreadedSaxpy(r, q, r, alpha, '-');
                          
             
        // |b|<=|r|*eps
                   
             
             sp = multithreadedScalarVectorProduct(r, r);
                       
             
             normr = Math.sqrt(sp);
             
          if (normr<=normb*eps) break;
             
        // beta = (r,r))/(r,r)(iter-1)
             
              beta = sp/spl;
              spl = sp;
             
             
        // z = r + beta*z;
             
              z = multithreadedSaxpy(r, z, z, beta, '+');
                         
      }while(true);
       
      deletedThreads();
     
      //sleep();
     
     
       return x;
   }
   
      
 void sleep(long millis){
     
     boolean f = false;
     
     try {
         do { 
            f = false;
            Thread.sleep(millis);
             for (int i = 0; i < threadsCount; i++) {
                 // Если хотя бы один из потоков работает продолжаем спать 
                 if (ts[i].getFlag()) {
                     f = true;
                     break;
                 }

             }

         } while (f);
     } catch (InterruptedException e) {
         System.out.println("Поток "+Thread.currentThread().getName() + " прерван");
     }
 }
     
 
 
 void deletedThreads(){
     
     for (int i=0;i<threadsCount;i++) ts[i].stop();
     
 }
         
       
    /**
     * Многопоточное скалярное произведение двух векторов
     * @param a  1-ый вектор
     * @param b  2-ой вектор
     * @return ret результат произведения
     */
 double multithreadedScalarVectorProduct(double[] a, double[] b ){
     
    double ret = 0.0;
   
     for (int i=0;i<threadsCount;i++) {               
              ts[i].setb(a);
              ts[i].setc(b);
              ts[i].setRet(ret);
              ts[i].setMode(2);
              ts[i].resume();   //                           
           }
     
   
     // ждем, пока все потоки зайдут в wait
    sleep(100);
   
    // собираем со всех потоков результат
    for (int i=0;i<threadsCount;i++) {
        ret+=ts[i].getRet();
    }
   
   return ret;   
           
 }
 
 
 /**
  * Многопоточное умножение матрицы на вектор c = A*b
  * @param A квадратная матрица, рамера [n x n]
  * @param b вектор на который происходит умножение, размера n
  * @param c вектор, размера n
  * @return с результат умножения матрицы на вектор
  */
 double[] multithreadedMatrixVectorProduct(double[][] A, double[] b, double[] c){
     
    for (int i=0;i<threadsCount;i++) {               
              ts[i].setA(A);
              ts[i].setb(b);
              ts[i].setResult(c);
              ts[i].setMode(1);
              ts[i].resume();                             
           }
     
     // ждем, пока все потоки зайдут в wait
    sleep(100);
               
  return c;   
 }
 
 
 /**
  * Многопоточная операция saxpy z = y 'ch' alpha*x 
  * @param y  вектор
  * @param x  вектор
  * @param z  вектор
  * @param koef  коэффициент умножения
  * @param ch символ сложения ('+') или вычитания ('-') 
  * @return z результат операции saxpy
  */
 double[] multithreadedSaxpy(double[] y, double[] x, double[] z, double koef, char ch){
     
    int mode = 0;
     if (ch == '+') mode = 3;
     else if (ch == '-') mode = 4;
     
     for (int i=0;i<threadsCount;i++) {               
              ts[i].setb(y);
              ts[i].setc(x);
              ts[i].setResult(z);
              ts[i].setKoef(koef);
              ts[i].setMode(mode);
              ts[i].resume();                             
           }
     
    // ждем пока все потоки зайдут в wait
     sleep(100);
   
     return z;
     
 }
 
 
 double multithreadedComputeVectorNorm(double[] b){
     
  double norm = 0.0;   
  norm = Math.sqrt(multithreadedScalarVectorProduct(b, b));
 
  return norm;
         
 }

int getIter(){
       return iter;
  }

}

Добавлено @ 14:48
Ну и конечно класс поток:

Код


class MyThread implements Runnable {
     
     Thread t;
     
     
    private int mode; // режим работы потока
     
     // mode 1 - Умножене матрицы на вектор
     // mode 2 - Скалярное умножение векторов
     // mode 3 - Операция saxpy (+)
     // mode 4 - Операция saxpy (-)
     // mode 5 - Вычисление нормы вектора
     
     
   private  double[][] A;
   private  double[] b;   
   private  double[] c;
   
   private double koef;
   private double[] result; 
   private volatile double ret;
     
     private boolean flag;
     
     private int begin;
     private int end;
     
     public MyThread(int begin, int end){
         
         t = new Thread(this);
         flag = false;
         this.begin = begin;
         this.end = end;
     }

     void start(){
         
         flag = true;
         t.start();
     }
     
    synchronized void resume() {
         flag = true;
         notify();
     }
     
     void stop(){
         t.interrupt();
         t = null;
     }
     
          
    public void run() {
       
        do {
           
       
             // приостаналиваем поток пока его не пробудят
            synchronized(this) {             
              try{
                flag = false; 
                 wait(); 
              }  catch(InterruptedException e){
                  // Если поток остановлен выходим из run()
                  return;
              }                                         
            }
           
           
                 
            switch(mode){
                case 1 : {
                    result = MatrixVectorOperations.computeMatrixVectorProduct(begin, end, A, b);
                    break;   
                }
                case 2 : {
                    ret = MatrixVectorOperations.scalarVectorsProduct(begin, end, b, c,ret);
                    break;
                }
                   
                case 3 : {
                    result = MatrixVectorOperations.saxpy(begin, end, b, c, result, koef, '+');
                    break;
                }
                   
                case 4 : {
                    result = MatrixVectorOperations.saxpy(begin, end, b, c, result, koef, '-');
                    break;
                }             
                case 5 :
                {
                    ret = MatrixVectorOperations.computeVectorNorm(begin, end, b);
                    break;
                }
                   
                default: break;
            }
           
           
                   
        } while(true);
       
       
    }
     
   
    void setA (double[][] A){       
        this.A = A;       
    }
   
    void setb (double[] b){
        this.b = b;
    }
   
    void setc(double[] c){
        this.c = c;
    }
     
   void setResult(double[] result){
       this.result = result;     
   }
   
   void setKoef(double koef){
       this.koef = koef;
   }
   
   void setRet(double ret){
       this.ret = ret;
   }
   
   void setMode(int mode){
       if (mode>0&&mode<5) this.mode = mode;
       else System.out.println("Неправильно задан режим работы потока");
   }
   
   boolean getFlag(){
       return flag;
   }
   
   double getRet(){
       return ret;
   }
   
 }

Добавлено через 10 минут и 13 секунд
Когда нужно выполнить какую- нибудь операцию (будь то умножение матрицы на вектор или произведение веторов или др.)
всем потокам задается соответсвующий режим и вызывается для каждого потока метод resume(), который вызывает в себе notify() и пробуждает поток. Каждый поток выполняет операцию, попадает в синхронизированный блок и засыпает вновь.
Пока все вычислительные потоки не заснут главный поток не должен ничего делать (т.е пока какая - либо операция полностью не завершится на всех потоках к следующей операции переходить нельзя), поэтому для главного потока него вызывается метод sleep().
Уже при n = 100 выполняется очень долго (около 100 секунд).
Причем практически не загружает процессор (при выполнении загрузка процессора 0-1%). Первый же метод (последовотельный) алгоритм загружает процессор как и должен на 50%, так как используется одно ядро.
Что то тут не так. При 2-ух потоках должен загружать машину (2-ух ядерный процессор) на 100%. Не могу разобратся что сделал не так.
Вообще нужно сделать как можно эффективнее. Как по другому реализовать работу потоков не знаю.
Вообщем нужна ваша помошь дорогие гуру.

Это сообщение отредактировал(а) x8m6 - 11.12.2008, 14:53

anonymouse

Дата 11.12.2008, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 18.8.2004

Репутация: нет
Всего: 1

Ну во первых кто вам сказал, что Java процессы будут распределяться равномерно на ваши процессоры.
Во вторых, попробуйте абстрагироваться и убрать все ваше описание задачи и сделать схему работы потоков. Я не очень вникал в задачу, но я не уверен что вам нужна многопоточность в данном случае. Ведь если процессы запускать параллельно то это еще не значит что все будет работать быстрее. Паралельность как правило требуется когда есть прерывания, когда процессор в связи со спецификой задачи простаивает.
В третих есть еще такая вещь как volatile для работы одним обьектом во многих потоках. Это чтобы не заморачиваться с wait и notify

Это сообщение отредактировал(а) anonymouse - 11.12.2008, 22:38

--------------------

Много чего интересного...

x8m6

Дата 11.12.2008, 23:12 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 156
Регистрация: 11.12.2008

Репутация: нет
Всего: нет

Цитата

Ну во первых кто вам сказал, что Java процессы будут распределяться равномерно на ваши процессоры.

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

Цитата

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

Как раз таки в этом случае и нужна. Специфика этого алгоритма такова что при параллельном запуске он должен работать быстрее.

Цитата

Паралельность как правило требуется когда есть прерывания, когда процессор в связи со спецификой задачи простаивает.

Как раз таки процессор и простаивает. (точнее не процессор а одно ядро процессора, в тот момент когда 2-ое нагружено полностью - но это при последовательном алгоритме).

Цель данной разработки именно использовать возможности современных многоядерных процессоров полностью, воспользовавшись встроенной многопоточностью в Java.
Ещё раз повторяю алгоритм должен хорошо распараллеливаться.
Посмотрите например здесь
http://www.intuit.ru/department/calculate/paralltp/8/5.html

Это сообщение отредактировал(а) x8m6 - 11.12.2008, 23:17

SoulKeeper

Дата 12.12.2008, 01:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Судя по картинке - сойдет что-то такое:

Код


package mathtests;

import java.util.concurrent.atomic.AtomicInteger;

public class ConjugateGradient {

    private AtomicInteger index = new AtomicInteger(0);

    private double[][] matrix;

    private double[] vector;

    public void calculate(){
        Thread[] threads = new Thread[getThreadCount()];
        for(int i = 0; i < threads.length; i++){
            Thread t = new Thread(new ComputingTask());
            threads[i] = t;
            t.start();
        }

        for(Thread t : threads){
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private int getThreadCount() {
        int processorCount = Runtime.getRuntime().availableProcessors();
        int matrixSize = matrix.length;

        if (matrixSize < processorCount) {
            return matrixSize;
        } else {
            return processorCount;
        }
    }

    public double[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(double[][] matrix) {
        this.matrix = matrix;
    }

    public double[] getVector() {
        return vector;
    }

    public void setVector(double[] vector) {
        this.vector = vector;
    }

    private class ComputingTask implements Runnable {

        public void run() {
            while (true) {
                int myIndex = index.getAndIncrement();
                if (myIndex >= matrix.length) {
                    break;
                } else {
                    processMatrixRow(myIndex);
                }
            }
        }

        private void processMatrixRow(int rowIndex) {
            double[] matrixRow = matrix[rowIndex];
            // TODO: Here we should do all work with matrix row
        }
    }

    public static void main(String[] args) {
        ConjugateGradient cg = new ConjugateGradient();
        cg.setMatrix(new double[10][10]);
        cg.setVector(new double[10]);
        cg.calculate();
    }
}

Тут нагрузка будет распределена на все доступные ядра процессора (ну или если количество єлементов меньше чем ядер, то вся матрица будет обрабатываться параллельно), поток будет брать следующий доступный рядок из матрицы и делать с ним то что будет написано вместо // TODO: Here we should do all work with matrix row

Но честно говоря я ничего с Вашей математики не понял smile

А Википедия так вообще испугала.

Это сообщение отредактировал(а) SoulKeeper - 12.12.2008, 02:01

x8m6

Дата 12.12.2008, 14:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 156
Регистрация: 11.12.2008

Репутация: нет
Всего: нет

Цитата

Все это конечно замечательно, но это не совсем то что мне надо. например мне нужно умножить матрицу на вектор:

Код


 private void processMatrixRow(int rowIndex) {
          //  double[] matrixRow = matrix[rowIndex];
            // TODO: Here we should do all work with matrix row
for (int i = 0;i<result.length;i++)  
            result[rowIndex] += matrix[rowIndex][i]*vector[i];                        
        }
 
        }

result -  это ещё один вектор класса ConjugateGradient.

В этом случае матрица "matrix" будет умножатся на вектор "vector" и результат будет записываться в вектор "result".
В вашем случае, после того как матрица будет полностью обработана потоки завершатся.

А мне нужно умножать матрицу на вектор в цикле (посмотрите пожалуйста внимательно ещё раз главный цикл шаг 4- шаг 8).
do {
q = A*z;
while();

Поэтому чтобы в цикле каждый раз заново не создавать потоки (что не есть good),  после умножения  я их приостанавливаю а на следующей итерации цикла перезапускаю. В вашем случае после умножения они все завершаются и чтобы на следующей итерации вновь произвести умножение нужно опять их создать. Тем более что кроме умножения матрицы вектор в главном цикле ещё 3 операции произведения векторов и 3 операции saxpy. В вашем случае  придется на каждой итерации главного цикла создавать [кол-во процессоров]*7 разных потоков. В конце итерации убивать их и на следующей итерации опять создавать.  А это не очень хорошо повлияет на производительность. Поэтому я и решил создать потоки всего один раз (ещё до начала вычислений) и уже в процессе вычислений управлять ими (назначая им режим работы - mode, и приостанавливая и перезапуская их когда нужно). Именно с приостановкой и перезапуском потоков возникают какие - то проблемы, поэтому и процессор всё время простаивает.

Цитата

Но честно говоря я ничего с Вашей математики не понял

Спрашивайте что не понятно я вам объясню.

Vurn

Дата 13.12.2008, 08:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 24.5.2007

Репутация: 2
Всего: 3

Ответил в javatalks.ru

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »