Проект РНФ

Конкурс РНФ:

Про­ве­де­ние фун­да­мен­таль­ных на­уч­ных ис­сле­до­ва­ний и по­ис­ко­вых на­уч­ных ис­сле­до­ва­ний от­дель­ны­ми на­уч­ны­ми груп­па­ми.

Проект:

Но­вые эф­фек­тив­ные ме­то­ды и про­грам­мы для вы­чис­ли­тель­но-тру­до­ем­ких за­дач при­ня­тия ре­ше­ний с ис­поль­зо­ва­ни­ем су­пер­ком­пью­тер­ных си­стем ре­корд­ной про­из­во­ди­тель­но­сти

Руководитель проекта:

Гер­гель Вик­тор Пав­ло­вич, ди­рек­тор ин­сти­ту­та ИТММ, д.т.н., проф.

Цель проекта

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

От­ли­чи­тель­ны­ми осо­бен­но­стя­ми про­блем ра­ци­о­наль­но­го вы­бо­ра, на ис­сле­до­ва­ние ко­то­рых ори­ен­ти­ро­ван пред­ла­га­е­мый про­ект, яв­ля­ют­ся сле­ду­ю­щие прин­ци­пи­аль­ные мо­мен­ты:

  • До­пу­сти­мость из­ме­не­ния по­ста­нов­ки за­дач мно­го­кри­те­ри­аль­ной мно­го­экс­тре­маль­ной оп­ти­ми­за­ции в про­цес­се по­ис­ка оп­ти­маль­ных ва­ри­ан­тов, ко­гда мо­жет по­тре­бо­вать­ся скор­рек­ти­ро­вать на­бор кри­те­ри­ев и огра­ни­че­ний, ва­рьи­ру­е­мых па­ра­мет­ров, об­ла­сти по­ис­ка и т.п.
  • Мно­го­экс­тре­маль­ность функ­ци­о­на­лов за­дач ра­ци­о­наль­но­го вы­бо­ра, что яв­ля­ет­ся ха­рак­тер­ным для наи­бо­лее слож­ных (клю­че­вых) про­блем вы­бо­ра оп­ти­маль­ных ва­ри­ан­тов в ши­ро­ком спек­тре на­уч­ных и тех­ни­че­ских при­ло­же­ний.
  • Су­ще­ствен­ная вы­чис­ли­тель­ная слож­ность пла­ни­ру­е­мых к ис­сле­до­ва­нию за­дач ра­ци­о­наль­но­го вы­бо­ра в силу того, что вы­чис­ле­ние зна­че­ний кри­те­ри­ев и огра­ни­че­ний осу­ществ­ля­ет­ся, как пра­ви­ло, в ре­зуль­та­те объ­ем­но­го вы­чис­ли­тель­но­го ана­ли­за слож­ных ма­те­ма­ти­че­ских мо­де­лей изу­ча­е­мых яв­ле­ний и си­стем.

Краткая аннотация проекта

До­сти­же­ние цели про­ек­та под­ра­зу­ме­ва­ет раз­ра­бот­ку ком­плек­са ма­те­ма­ти­че­ских мо­де­лей, ме­то­дов и про­грамм­ных средств, охва­ты­ва­ю­щих как из­вест­ные, так и но­вые по­ста­нов­ки за­дач оп­ти­ми­за­ции (с ча­стич­но вы­чис­ли­мы­ми, не всю­ду опре­де­лен­ны­ми, раз­рыв­ны­ми функ­ци­о­на­ла­ми).

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

Все раз­ра­бо­тан­ные при вы­пол­не­нии про­ек­та ал­го­рит­мы бу­дут тео­ре­ти­че­ски обос­но­ва­ны и экс­пе­ри­мен­таль­но апро­би­ро­ва­ны при ре­ше­нии те­сто­вых и при­клад­ных за­дач с ис­поль­зо­ва­ни­ем су­пер­ком­пью­те­ра «Ло­ба­чев­ский».

Дополнительная информация о проекте

Значимость решаемой проблемы

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

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

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

До­пол­ни­тель­ным клю­че­вым мо­мен­том в за­да­чах оп­ти­маль­но­го вы­бо­ра яв­ля­ет­ся прин­ци­пи­аль­ная слож­ность опре­де­ле­ния од­но­го един­ствен­но­го кри­те­рия оп­ти­маль­но­сти. Как ре­зуль­тат, во мно­гих си­ту­а­ци­ях оп­ти­маль­но­го вы­бо­ра для оцен­ки эф­фек­тив­но­сти срав­ни­ва­е­мых ва­ри­ан­тов опре­де­ля­ет­ся на­бор част­ных кри­те­ри­ев оп­ти­маль­но­сти (та­ких, на­при­мер, как вес, сто­и­мость, гру­зо­подъ­ем­ность и т.п.). Дан­ные кри­те­рии в боль­шин­стве слу­ча­ев яв­ля­ют­ся про­ти­во­ре­чи­вы­ми, ко­гда улуч­ше­ние ка­че­ства при­ни­ма­е­мых ре­ше­ние по од­но­му кри­те­рию мо­жет при­во­дить к ухуд­ше­нию эф­фек­тив­но­сти по дру­го­му кри­те­рию (так, на­при­мер, сни­же­ние веса в ле­таль­ных ап­па­ра­тах при­во­дит, как пра­ви­ло, к сни­же­нию даль­но­сти по­ле­та). В та­ких си­ту­а­ци­ях, как пра­ви­ло, за­да­ют­ся те или иные ко­эф­фи­ци­ен­ты важ­но­сти част­ных кри­те­ри­ев, что поз­во­ля­ет со­гла­со­вы­вать вклад каж­до­го част­но­го кри­те­рия в ито­го­вое ком­про­мисс­ное ре­ше­ние за­да­чи оп­ти­маль­но­го вы­бо­ра. Опре­де­ле­ние зна­че­ний ко­эф­фи­ци­ен­тов важ­но­сти тоже пред­став­ля­ет со­бой от­дель­ную про­бле­му и, как ре­зуль­тат, за­да­чи оп­ти­маль­но­го вы­бо­ра ча­сто при­хо­дит­ся ре­шать мно­го­крат­но для по­лу­че­ния раз­ных ком­про­мисс­ных ва­ри­ан­тов вы­бо­ра.

Ключевые особенности подхода

В ос­но­ву вы­пол­не­ния про­ек­та по­ло­же­ны сле­ду­ю­щие ос­нов­ные по­ло­же­ния.

  1. Прин­цип по­сле­до­ва­тель­ной де­ком­по­зи­ции ре­ша­е­мых за­дач к ре­ше­нию од­ной или несколь­ко за­дач мень­шей слож­но­сти. В рам­ках дан­но­го под­хо­да:
  • Ре­ше­ние за­да­чи вы­бо­ра оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов сво­дит­ся к ре­ше­нию од­ной или несколь­ких за­дач мно­го­кри­те­ри­аль­ной оп­ти­ми­за­ции;
  • Ре­ше­ние мно­го­кри­те­ри­аль­ной за­да­чи сво­дит­ся к ре­ше­нию ска­ляр­ных за­дач нели­ней­но­го про­грам­ми­ро­ва­ния;
  • Ре­ше­ние за­дач нели­ней­но­го про­грам­ми­ро­ва­ния сво­дит­ся к ре­ше­нию без­услов­ных за­дач мно­го­экс­тре­маль­ной оп­ти­ми­за­ции.

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

  1. Ре­дук­ция раз­мер­но­сти с ис­поль­зо­ва­ни­ем раз­вер­ток Пе­а­но для све­де­ния ре­ше­ния мно­го­мер­ных оп­ти­ми­за­ци­он­ных за­дач к ре­ше­нию од­ной или несколь­ких свя­зан­ных од­но­мер­ных за­дач. Дан­ный под­ход поз­во­ля­ет су­ще­ствен­но сни­зить остро­ту про­бле­мы «про­кля­тия раз­мер­но­сти» (зна­чи­тель­ное уве­ли­че­ние объ­е­ма вы­чис­ле­ний при по­вы­ше­нии раз­мер­но­сти ре­ша­е­мых за­дач) и яв­ля­ет­ся од­ним из наи­бо­лее про­дук­тив­ным на­прав­ле­ни­ем раз­ра­бот­ки но­вых эф­фек­тив­ных ме­то­дов мно­го­экс­тре­маль­ной оп­ти­ми­за­ции.
  2. При­ме­не­ние вы­со­ко­про­из­во­ди­тель­ных па­рал­лель­ных ал­го­рит­мов гло­баль­но­го по­ис­ка, раз­ра­бо­тан­ных в рам­ках ин­фор­ма­ци­он­но-ста­ти­сти­че­ской тео­рии мно­го­экс­тре­маль­ной оп­ти­ми­за­ции, ко­то­рая пред­став­ля­ет со­бой один из клю­че­вых ре­зуль­та­тов Ни­же­го­род­ской на­уч­ной шко­лы мно­го­экс­тре­маль­ной оп­ти­ми­за­ции. Дан­ные ал­го­рит­мы от­но­сят­ся к чис­лу ли­ди­ру­ю­щих по эф­фек­тив­но­сти ме­то­дов гло­баль­но­го по­ис­ка и по­ка­за­ли свою вы­со­кую про­дук­тив­ность при ре­ше­нии мно­гих слож­ных за­дач мно­го­экс­тре­маль­ной оп­ти­ми­за­ции.

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

Ос­нов­ным ре­зуль­та­том вы­пол­не­ния про­ек­та бу­дет яв­лять­ся раз­ра­бот­ка па­рал­лель­ных вы­чис­ли­тель­ных схем, эф­фек­тив­но мас­шта­би­ру­е­мых вплоть до ис­поль­зо­ва­ния со­тен ты­сяч вы­чис­ли­тель­ных ядер, зна­чи­тель­но рас­ши­ря­ю­щих класс ре­ша­е­мых за­дач на ос­но­ве ис­поль­зо­ва­ния вы­чис­ли­тель­ных мощ­но­стей суперкомпью­терных си­стем но­во­го — тран­спе­тафлопсно­го — уров­ня про­из­во­ди­тель­но­сти.

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

  1. Ма­те­ма­ти­че­ская мо­дель вы­бо­ра оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов, охва­ты­ва­ю­щая мно­гие из­вест­ные по­ста­нов­ки за­дач оп­ти­ми­за­ции. Дан­ный ре­зуль­тат пред­став­ля­ет­ся зна­чи­мым, по­сколь­ку поз­во­лит сфор­ми­ро­вать еди­ный под­ход для ре­ше­ния за­дач вы­бо­ра вме­сто ис­поль­зо­ва­ния мно­же­ства част­ных по­ста­но­вок.
  2. Ма­те­ма­ти­че­ская мо­дель про­цес­са по­ис­ка оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов, преду­смат­ри­ва­ю­щая воз­мож­ность из­ме­не­ния по­ста­нов­ки за­да­чи вы­бо­ра (на­бо­ра кри­те­ри­ев и огра­ни­че­ний, ва­рьи­ру­е­мых па­ра­мет­ров, об­ла­сти по­ис­ка). Фор­му­ли­ро­ва­ние та­кой мо­де­ли поз­во­лит бо­лее адек­ват­но про­во­дить мо­де­ли­ро­ва­ние про­цес­сов по­ис­ка оп­ти­маль­ных (неулуч­ша­е­мых) ва­ри­ан­тов в слож­ных си­ту­а­ци­ях вы­бо­ра.
  3. Но­вый под­ход к ре­ше­нию за­дач мно­го­кри­те­ри­аль­ной оп­ти­ми­за­ции с мно­го­экс­тре­маль­ны­ми кри­те­ри­я­ми и нели­ней­ны­ми огра­ни­че­ни­я­ми, поз­во­ля­ю­щий по­лу­чать как част­ные, так и пол­ные оцен­ки мно­же­ства неулуч­ша­е­мых (оп­ти­маль­ных по Па­ре­то) ва­ри­ан­тов. Зна­чи­мость дан­но­го ре­зуль­та­та со­сто­ит в том, что при ре­ше­нии но­вых воз­ни­ка­ю­щих ска­ляр­ных за­дач оп­ти­ми­за­ции бу­дет ис­поль­зо­вать­ся по­ис­ко­вая ин­фор­ма­ция, по­лу­ча­е­мая на всех пред­ше­ству­ю­щих эта­пах вы­чис­ле­ний. Дан­ный под­ход поз­во­лит су­ще­ствен­но со­кра­тить тре­бу­е­мый объ­ем вы­чис­ле­ний, что даст воз­мож­ность ана­ли­за бо­лее ши­ро­ко­го спек­тра ва­ри­ан­тов для вы­бо­ра наи­бо­лее со­от­вет­ству­ю­щих по­ня­тию оп­ти­маль­но­сти.
  4. Мо­дель ин­фор­ма­ци­он­но­го со­про­вож­де­ния про­цес­са по­ис­ка оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов, обес­пе­чи­ва­ю­щая на­коп­ле­ние, хра­не­ние, эф­фек­тив­ную об­ра­бот­ку и по­втор­ное ис­поль­зо­ва­ние всей по­лу­ча­е­мой в про­цес­се вы­чис­ле­ний по­ис­ко­вой ин­фор­ма­ции. Дан­ный ре­зуль­тат яв­ля­ет­ся од­ним из клю­че­вых в рам­ках про­ек­та, по­сколь­ку обес­пе­чи­ва­ет прак­ти­че­скую ос­но­ву для при­ме­ни­мо­сти всех раз­ра­ба­ты­ва­е­мых мо­де­лей и ме­то­дов. Ре­ше­ние даже един­ствен­ной по­ста­нов­ки за­да­чи вы­бо­ра яв­ля­ет­ся чрез­вы­чай­но слож­ной вы­чис­ли­тель­ной про­бле­мой – ре­ше­ние же всех воз­ни­ка­ю­щих при из­ме­не­нии по­ста­но­вок за­дач яв­ля­ет­ся пол­ное по­втор­ное ис­поль­зо­ва­ние все по­ис­ко­вой ин­фор­ма­ции, по­лу­ча­е­мой в про­цес­се вы­чис­ле­ний.
  5. Ин­те­гри­ро­ван­ное се­мей­ство ме­то­дов ре­ше­ния за­дач мно­го­кри­те­ри­аль­ной мно­го­экс­тре­маль­ной оп­ти­ми­за­ции с невы­пук­лы­ми огра­ни­че­ни­я­ми, до­пус­ка­ю­щие по­втор­ное ис­поль­зо­ва­ние име­ю­щей­ся по­ис­ко­вой ин­фор­ма­ции и ко­то­рые мо­гут быть эф­фек­тив­но рас­па­рал­ле­ле­ны для су­пер­ком­пью­тер­ных си­стем с ка­че­ствен­но но­вым уров­нем воз­мож­но­го па­рал­ле­лиз­ма (вплоть до мил­ли­о­нов вы­чис­ли­тель­ных устройств). Про­бле­ма прак­ти­че­ско­го ис­поль­зо­ва­ния вы­чис­ли­тель­но­го по­тен­ци­а­ла со­вре­мен­ных су­пер­ком­пью­тер­ных си­стем име­ет прин­ци­пи­аль­ное зна­че­ние прак­ти­че­ски для все­го спек­тра вы­чис­ли­тель­ных наук.
  6. Схе­ма па­рал­лель­ных вы­чис­ле­ний в за­да­чах мно­го­кри­те­ри­аль­ной мно­го­экс­тре­маль­ной оп­ти­ми­за­ции, ори­ен­ти­ро­ван­ных на мас­со­вый па­рал­ле­лизм для су­пер­ком­пью­тер­ных си­стем но­во­го – тран­спе­тафлопсно­го – уров­ня про­из­во­ди­тель­но­сти. Дан­ный ре­зуль­тат от­но­сит­ся к чис­лу осо­бо зна­чи­мых в рам­ках про­ек­та, по­сколь­ку поз­во­лит прак­ти­че­ски ис­поль­зо­вать ко­лос­саль­ный вы­чис­ли­тель­ный по­тен­ци­ал со­вре­мен­ных су­пер­ком­пью­тер­ных за­дач. Раз­ра­бо­тан­ные мо­де­ли и ме­то­ды сов­мест­но со схе­мой ор­га­ни­за­ции эф­фек­тив­ных па­рал­лель­ных вы­чис­ле­ний поз­во­лит по­вы­сить не ме­нее чем на по­ря­док слож­ность ре­ша­е­мых за­дач вы­бо­ра оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов.
  7. Ин­те­гри­ро­ван­ная про­грамм­ная си­сте­ма, ре­а­ли­зу­ю­щая раз­ра­бо­тан­ные в рам­ках про­ек­та мо­де­ли и ме­то­ды для ре­ше­ния за­дач вы­бо­ра оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов. Но­виз­на со­зда­ва­е­мой про­грамм­ные си­сте­мы со­сто­ит преж­де все­го в ее ма­те­ма­ти­че­ском и ал­го­рит­ми­че­ском на­пол­не­нии. Под­дер­жи­ва­е­мые в ре­зуль­та­те ис­поль­зо­ва­ния си­стем про­цес­сы по­ис­ка оп­ти­маль­ных (наи­луч­ших) ва­ри­ан­тов бу­дут бо­лее адек­ват­но со­от­вет­ство­вать тео­рии и прак­ти­ки ре­ше­ния за­дач вы­бо­ра. Воз­мож­ность ис­поль­зо­ва­ния зна­чи­тель­но­го чис­ла вы­чис­ли­тель­ных эле­мен­тов (вплоть до со­тен ты­сяч вы­чис­ли­тель­ных ядер) пред­став­ля­ет зна­чи­мый ре­зуль­тат и бу­дет пре­вы­шать все до­стиг­ну­тые ре­зуль­та­ты рос­сий­ски­ми и за­ру­беж­ны­ми ис­сле­до­ва­те­ля­ми в об­ла­сти тео­рии и прак­ти­ки про­блем вы­бо­ра ва­ри­ан­тов. Раз­ра­бо­тан­ная про­грамм­ная си­сте­ма бу­дет до­ве­де­на по про­мыш­лен­но­го ис­поль­зо­ва­ния для ре­ше­ния ак­ту­аль­ных прак­ти­че­ских за­дач вы­бо­ра в раз­ных об­ла­стях при­ло­же­ний (на­при­мер, в со­ста­ве си­стем ав­то­ма­ти­зи­ро­ван­но­го про­ек­ти­ро­ва­ния).
Все новости