ua     ru    Sitemap   Sitemap     | Поиск... |       Сайт открыт 14.12.2005

Ukraine - Distributed Computing Team

 

 » Навигация 
  Новости
  Новости (Архив)
  Описания проектов
  Наши опросы
  Архивы

  Форум
  Форум (PDA)

 » Статьи  


       Описания проектов 
Начало раздела > Sztaki

О проекте Sztaki Desktop Grid



Версія українською

сбор информации - nikelong, Перевод Андреева Александра (AlexA), команда "Russia Team"



 

 

Проект Sztaki Desktop Grid

 

Это текст, размещенный на сайте szdg.narod.ru

Что такое SZTAKI?

Это странное слово - сокращение венгерского названия института Számítástechnikai és Automatizálási Kutató Intézet  (MTA SZTAKI is the Hungarian acronym for "The Computer and Automation Research Institute, Hungarian Academy of Sciences").

Проектом, который мы считаем (SZTAKI Desktop Grid – распределенный сетевой проект SZTAKI для настольных ПК) занимается лаборатория этого института (The Laboratory of Parallel and Distributed Systems of MTA SZTAKI Computer and Automation Research Institute), специализирующаяся на кластерных и Grid технологиях.

В настоящее время  считается проект BinSYS (он относится скорее не к математике, а к теории информации), но он не единственный (точнее - единственный под boinc, для широкой общественности). Остальные проекты в лаборатории осуществляются на внутренних Grid сетях (там и метеорология  и моделирование климата, и биохимические проекты, и работы над DSP – сигнальными процессорами). См. здесь.

В августе прошлого года закончилась предыдущая фаза исследований (с матрицами 10 измерения). Было обработано свыше 90 тысяч матриц, из которых достойными дальнейшего исследования оказались 383 матрицы. Как сообщается, было найдено три самых интересных матрицы. Имена участников, нашедших их приводятся на странице проекта.

В декабре 2005 г. закончилась работа с 11-м измерением. Теперь работают с матрицами 12 измерения.

 

   Краткое описание проекта.

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

Теоретическое отступление:

В жизни нам наиболее часто приходится сталкиваться с десятичной системой счисления, в которой используется 10 цифр, а основанием является число 10. Компьютерщикам близка двоичная система, с основание 2 и использованием 2-х цифр. Существует множество других систем счисления. Каждая из них имеет свои достоинства и недостатки. Например, в двоичной системе нельзя непосредственно записать отрицательные числа и приходится вводить дополнительные условия или признаки. Данную проблему можно решить взяв за основание число "-2". Тогда при четных степенях числа будут получаться положительные числа, а при нечетных отрицательные. Еще более интересные математические возможности дает использование в качестве основы не числа, а матрицы. В этом случае любой целочисленный вектор можно представить как конечное число нулей и единиц. Однако нахождение подходящих матриц дело не простое. На данный момент нет универсального и эффективного метода нахождения таких подходящих матриц. При успешном нахождении искомых систем счисления они могут найти эффективное применение в таких областях как сжатие данных, кодирование и шифрование информации. Кроме того, они интересны с геометрической точки зрения для изучения фрактальных наборов данных - одного из перспективных современных математических направлений.

Нахождением таких "хороших" матриц вплоть до 11 порядка (т.е. 11 на 11 элементов, и даже до 12-го) и занимается проект SZTAKI Desktop Grid. Несмотря на огромный объем необходимых вычислений проект хорошо поддается распараллеливанию и удачно вписывается в концепцию распределенных вычислений.





Перевод описания проекта BinSYS (теория проекта)


Цели.
Цель проекта состоит в том, чтобы найти все обобщенные двоичные системы счисления до 11-го измерения . Ниже мы даем короткое описание понятия системы счисления и упоминаем несколько возможных использований.

 [Работа по 11-му измерению закончена в декабре 2005 г. Теперь ведется работа с 12-м измерением. Прим. AlexA]


Введение.
Пусть n - целое число, больше единицы. Когда мы говорим о системах счисления в подлинном смысле, мы используем тот факт, что каждое натуральное число z может быть написано однозначно в конечной форме

 


Здесь, n – основа системы счисления, dj - положительное число. Если n=2, то это двоичная система счисления. Такие системы слишком слабы, чтобы представить отрицательные числа, поэтому приходится устанавливать признак числа. Однако, если допустить основе быть отрицательным целым числом, представление всех целых чисел становится возможным. Так например если мы используем основу -2, каждое целое число имеет форму

 


Это может быть обобщено для алгебраических целых чисел конечного расширения рациональной области числа. Простой пример: все Гауссовы целые числа (комплексные числа формы x+yi, где x, y - целые числа), может быть однозначно записаны с основой (-1+i) следующим образом

 

Используя линейную алгебру мы можем определить системы счисления еще более общим способом. Основой здесь является матрица, а цифрами - векторы. Мы можем повторно сформулировать предыдущий пример. Каждый двумерный целочисленный вектор имеет представление как конечная сумма,

 ,


где


и  .


 Мы говорим о двоичной системе счисления, если детерминант М +2. В этом случае есть только две цифры, одна из них является источником. Это означает, что, если мы имеем систему подобную счисления тогда, каждый целочисленный вектор может быть представлен как конечный ряд 0-й и 1-ц.

 
Не каждая матрица М может быть основой системы счисления. До сих пор описания "хороших" матриц не удались. Есть достаточные условия, и есть необходимые, но промежуток между ними является слишком большим. Нет никакого известного эффективного метода распределения матриц, для которых выполняются необходимые условия, но отсутствуют достаточные условия. Нужно отметить только одно - то, что, если мы устанавливаем детерминант и измерение, тогда можно говорить, что существует конечное число возможных матриц.

 

Ожидаемые результаты

Программа пытается найти множество обобщенных двоичных систем счисления. Обширный поиск выполняется в конечном множестве матриц данного размера, выполняющего некоторые необходимые условия. Трудность состоит в том, что размер этого конечного множества является функцией экспоненциальной измерению. Теперь появилась возможность заняться изучением матриц11х11 . Чтобы проверять далее необходимые условия, программа выполняет большое вычисление с плавающей запятой. Таким образом, необходимы большие затраты процессорного времени . К счастью, возможна параллельная обработка, и мы можем извлечь выгоду из выполнения программы на нескольких машинах.

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

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

 Системы счисления также интересны с геометрической точки зрения. Если мы позволяем отрицательным степеням М появляться в двоичном представлении, мы получаем возможно бесконечного представления реальных векторов (можно сказать, что мы используем показатель основания системы счисления). Граница набора векторов с двоичным представлением, содержащим только отрицательные степени М (набор H чисел с нулевой целочисленной частью) имеет главным образом дробное измерение (это - "фрактал"). Вывод программы может использоваться, чтобы проанализировать эти наборы. Это означает топологический анализ, например вычисление измерения, связность и т.д. Если мы используем матрицу М, приведенную выше, мы получаем следующий набор.

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

 


Для более детального знакомства с проектом можно посетить этот сайт.





Результаты работы по проекту BinSys


УСПЕХ!
Выполнение программы закончилось в конце декабря 2005, благодаря большому числу компьютеров, связанных Grid-сетью. Цель состояла в том, чтобы получить полный список полиномов (многочленов) 11 степени с постоянным периодом 2 и ведущим коэффициентом 1. Среди них можно найти все обобщенные двойные основы системы счисления.

 
Вывод программы
 Программа генерировала 550 полиномов. При написании программы мы должны были позволить ей производить больший вывод, чем фактический набор экспансивных полиномов. Это необходимо для оптимизации скорости. В общей сложности оказалось, что 338 полиномов были экспансивными. (Остальные могут быть описаны как продукт экспансивных и циклических (cyclotomic) полиномов. Эти полиномы также интересны , именно поэтому мы не включаем в программу дополнительный код, чтобы избавиться от них.)

 
Полиномы систем счисления
Мы использовали определенный алгоритм, чтобы определить, какие экспансивные полиномы являются полиномами систем счисления. Эта процедура выполнена в Университете Eotvos Lorand, Будапешт. Как мы и ожидали, только несколько полиномов оказались полиномами систем счисления. Их точное число - 11. Ниже мы приводим полный список, содержащий число экспансивных полиномов и полиномов систем счисления до 11-го измерения.

Степень
 23
4
5
6
7
8
9
10
11
 Экспансивных 57
29
29
105
95
309
192
619
338
 Систем счисления
4
4
12
7
25
12
20
12
40
11

Числа в таблице и скорости увеличения в степенных периодах - интересная проблема и будет подвергнута нашему математическому исследованию.

 
Дальнейшие проекты
Полученные системы счисления проверяются в приложениях, связанных со сжатием данных и т.д. Кроме того, происходит математический анализ .

Далее работа в этой области включает два непосредственных обобщения. С одной стороны, измерения выше чем 12 могли подвергнуться изучению с помощью, в настоящее время, недоказанной математической догадки. Использование этой догадки могло бы уменьшить объем непосредственных параметров так, чтобы список полиномов мог быть получен. Мы уверены, что этот список не будет полным на 100 %, но с практической точки зрения, возможно и неполный список будет ценен. Эта программа теперь выполняется  для степени 12.

Обобщение проблемы имеет дело с полиномами с постоянным периодом, больше чем 2. В случай постоянного периода 3, мы говорим об обобщенных троичных системах счисления. В настоящее время программа для троичных систем счисления находится в фазе развития. Мы оцениваем, можем ли мы генерировать полный список канонических троичных систем счисления до степеней 9 или 10. Эта программа будет запускает в режиме распределенных (параллельных) сетевых вычислений.


Обсудить проект и узнать как к нему подключится можно на нашем форуме.


Дата: Воскресенье, 20 Июль 2008
Прочитана: 8480 раз

Распечатать Распечатать    Переслать Переслать    В избранное В избранное

Другие публикации
  • FAQ по SZTAKI Desktop Grid
    Вернуться назад

  •  » Поддержка (обращайтесь) 
    Folding@Home
     NikeLong246659609
     Alex266184514
     ReMMeR338177212
    Rosetta@Home
     uNiUs172324149
     KoDak313871706
    World Community Grid
     Dmitrio250896826
    FightAIDS@Home
     RHAngel50177406
    RC5/OGR
     Tamagoch53619819
     Paul B.Atton46941577
    Seti@Home
     Andrey Fenchenko285577622
    WebMaster
     ReMMeR338177212
     Rilian (PM)1
    Поболтать
     Dead J. Dona122008482