Заявлен "Способ вычислений на многопроцессорном кластере", совокупность признаков которого изложена в формуле, представленной на дату подачи заявки в следующей редакции:
«1. Способ вычислений на многопроцессорном кластере, процессоры которого соединены посредством коммуникационной среды, способной передавать сообщение между любыми двумя из n процессоров кластера, заключающийся в том, что алгоритм решения задачи организуется так, чтобы графом алгоритма являлось взвешенное дерево, у которого веса исходящих ребер, инцидентных одной вершине, соответствовали очередности вычислений поддеревьев, начинающихся с этих ребер, а совпадение весов ребер соответствовало одновременности вычислений поддеревьев, начинающихся с этих ребер, чтобы входные данные задачи поступали в корневую вершину дерева, и результат решения задачи получался в корневой вершине; при этом в вершинах дерева расположены вычислительные блоки, потоки данных направляются по ребрам дерева от корневой вершины к листьям, а затем в обратном направлении; вычислительный блок в вершине дерева с весами исходящих ребер 1..h разбивается на отдельные вычислительные подблоки 0..h, 4 при этом 0-ой подблок вычисляется после получения входных данных, полученных по входному ребру, j-тый подблок (j=1..h) вычисляется после получения результатов вычислений по всем поддеревьям, начинающимся с исходящих ребер веса j; каждый процессор совершает вычисления по поддеревьям дерева алгоритма, множество вершин поддеревьев, вычисляемых всеми процессорами, образует разбиение множества вершин дерева алгоритма; передача данных по ребрам, соединяющим вершины поддеревьев, вычисляемых разными процессорами, осуществляется путем передачи сообщений через коммуникационную среду.
2. Способ вычислений на многопроцессорном кластере по п.1, отличающийся тем, что поддеревья, вычисление которых осуществляется быстрее на одном процессоре, чем при распараллеливании; выявляются экспериментально и объявляются листовыми вершинами.
3. Способ вычислений на многопроцессорном кластере по п.2, отличающийся тем, что 1-ый процессор получает корневую вершину дерева, входные данные всего алгоритма и список «подчиненных» процессоров 1,2,..,n; процессор s (s=1..n) получает корневую вершину V своего поддерева, входные данные для этой вершины и список «подчиненных» процессоров s,s+1,..,t, затем, начиная с i=1 и кончая i=h, где 1..h - веса ребер, исходящих из вершины V, производится параллельное вычисление поддеревьев, начинающихся со всех v(i) исходящих ребер веса i вершины V, для этого список «подчиненных» процессоров s,s+1,..,t и список ребер веса i делятся на w(i)=min(v(i), t-s+1) частей, вершины, связанные с V через ребра первой части списка ребер веса i, передаются процессору s и добавляются к его поддереву, с ними передается первая часть списка «подчиненных» процессоров; вершины, связанные с V через ребра j-той (j=2..w(i)) части списка ребер веса i, вместе с j-той частью списка «подчиненных» процессоров передается первому процессору в j-той части списка; если процессор s получает только один «подчиненный» процессор 5 или полученная им вершина дерева V является листовой, то все поддерево, начинающееся с этой вершины он вычисляет сам.
4. Способ вычислений на многопроцессорном кластере по п.2, отличающийся тем, что один процессор кластера выполняет функцию диспетчера, которая состоит в том, что он создает список свободных (СП) и список загруженных (ЗП) процессоров; в начальный момент СП содержит список 2,3, ..,n, а ЗП пуст, 1-ый процессор получает корневую вершину дерева алгоритма и входные данные задачи; процессор s получает корневую вершину V своего поддерева и, начиная с i=1 и кончая i=h, где 1..h - веса ребер, исходящих из вершины V, организует независимое вычисление поддеревьев, начинающихся со всех v(i) исходящих ребер веса i, для этого запрашивает у диспетчера v(i)-1 свободных процессоров, он получает либо запрошенный список, либо только f имеющихся в этот момент в СП свободных процессоров (f<v(i)) и передает каждому из них по одной вершине, а вершины f+1,..,v(i) оставляет в своем поддереве, если при этом f+1<v(i), то процессор s посылает диспетчеру сообщение о добавлении своего номера в ЗП; если процессор s вычислил все полученное им поддерево, то он сообщает диспетчеру, что s - свободный процессор и, если ЗП пуст, то s добавляется в СП, а если список ЗП не пуст, то s направляется диспетчером первому процессору z в ЗП; процессор z, получив свободный процессор s от диспетчера, передает ему корневую вершину того поддерева у своего поддерева, вычисление которого еще не начиналось, а если таких поддеревьев нет, то z посылает диспетчеру сообщение об удалении себя из ЗП и посылает диспетчеру процессор s, как свободный.
5. Способ вычислений на многопроцессорном кластере по п.4 отличающийся тем, что в списке ЗП сохраняются по два числа - номер процессора s и самый низкий уровень L(s) вершины (уровень вершины - это число ребер, которые лежат на пути от корневой вершины до данной) в поддереве этого процессора, которая не вычислялась на момент записи в ЗП; ЗП 6 сортируется в порядке увеличения чисел L(s); каждый процессор s при изменении числа L(s) посылает сообщение диспетчеру, и диспетчер вносит изменение в ЗП; процессор z, получив номер свободного процессора s от диспетчера, передает процессору s корневую вершину того поддерева у своего поддерева, вычисление которого еще не начиналось и которая имеет самый низкий уровень, а если такого поддерева нет, то z посылает диспетчеру сообщение об удалении своего номера из ЗП и посылает диспетчеру номер вершины s, как свободной.
6. Способ вычислений на многопроцессорном кластере по п.3, отличающийся тем, один процессор кластера выполняет функцию диспетчера, которая состоит в том, что он создает список свободных (СП) и список загруженных (ЗП) процессоров, в начальный момент оба списка пустые; если процессор s получает один «подчиненный» процессор s и список вершин {V}, связанных с одной и той же вершиной исходящими из нее ребрами одинакового веса, то он сам вычисляет все поддеревья, для которых вершины {V} являются корневыми и, если {V} содержит более одной вершины, то s посылает диспетчеру сообщение о записи его в ЗП; если процессор s вычислил все полученное им поддерево, то он посылает диспетчеру сообщение о записи его в СП; если процессор s получает корневую вершину V своего поддерева и список «подчиненных» процессоров s,s+1,..,t и вершина V является листовой, то s посылает диспетчеру сообщение о записи s+1,..,t в СП; как только оба списка ЗП и СП становятся непустыми, диспетчер посылает всем процессорам кластера сообщение «включен диспетчерный режим»; для вычисления процессором s в состоянии «включен диспетчерный режим» поддеревьев, начинающихся со всех v(i) исходящих ребер веса i вершины V, он посылает запрос диспетчеру о v(i)-1 свободном процессоре, получает запрошенный список либо только f имеющихся в этот момент в СП свободных процессоров (f<v(i)) и передает каждому из них по одной вершине, а вершины f+1,..,v(i) оставляет себе, если 7 при этом f+1<v(i), то s посылает диспетчеру сообщение о добавлении s в ЗП; если процессор s вычислил все полученное им поддерево, то он посылает диспетчеру сообщение, что s свободен; диспетчер, получив сообщение о свободном процессоре s, добавляет s в СП, если список ЗП пуст, иначе s направляется диспетчером первому процессору z в списке ЗП; процессор z, получив сообщение о свободном процессоре s от диспетчера, посылает процессору s сообщение, в котором передает s корневую вершину того поддерева у своего поддерева, вычисление которого еще не начиналось, а если такого нет, то z посылает диспетчеру сообщение о вычеркивании себя из списка ЗП и посылает диспетчеру вершину s, как свободную; как только список СП достигает длины n-1 диспетчер посылает всем процессорам кластера сообщение «выключен диспетчерный режим», очищает оба списка ЗП и СП, а первый процессор устанавливает в корневой вершине список «подчиненных» процессоров 2..n.
7. Способ вычислений на многопроцессорном кластере по п.6, отличающийся тем, что в списке ЗП сохраняются по два числа - номер процессора s и самый низкий уровень вершины L(s) (уровень вершины - это число ребер, которые лежат на пути от корневой вершины до данной) в поддереве этого процессора, которая не вычислялась на момент записи в ЗП; ЗП сортируется в порядке увеличения чисел L(s); каждый процессор s при увеличении числа L(s) посылает об этом сообщение диспетчеру, а диспетчер, получив такое сообщение, вносит изменение в список ЗП; процессор z, получив свободный процессор s от диспетчера, передает процессору s корневую вершину того поддерева у своего поддерева, вычисление которого еще не начиналось и которая имеет самый низкий уровень, а если такого нет, то z посылает диспетчеру сообщение о вычеркивании себя из списка ЗП и посылает диспетчеру вершину s, как свободную.
8
8. Способ вычислений на многопроцессорном кластере по п.2, отличающийся тем, что при каждой вершине дерева алгоритма создается изначально пустой список дополнительных процессоров (ДП), а при вычислении v(i) поддеревьев, которые начинаются с ребер веса i (i=1,..,h) вершины V, создается регистр из v(i) флагов ребер веса i и один флаг вершины V; каждый флаг ребра принимает значения 0,1,2: 2 - закончено вычисление поддерева начинающегося с этого ребра, 1 - начаты вычисления всех листовых вершин поддерева, начинающегося с этого ребра. 0 - в остальных случаях; в процессе вычисления поддеревьев, начинающихся с ребер веса i вершины V флаг вершины V принимает значения 0,1,2: значение 2 - когда i=h, все флаги ребер веса h равны 2 и вычислен подблок h, значение 1 - когда значение не равно 2 и нет 0 - флагов ребер веса i, 0 - в остальных случаях; при переходе к вычислению ребер очередного веса флаги обнуляются; при изменении одного из флагов ребер веса i вершины V пересчитывается флаг вершины V, для этого используется счетчик N0 числа флагов 0 и счетчик Nh2 числа флагов 2 при i=h; когда Nh2=v(h) и закончено вычисление подблока h вершины V, то флаг вершины V принимает значение 2, в противном случае, если N0=0, то флаг вершины V принимает значение 1, иначе он равен 0; если V корневая вершина дерева, и ее флаг принял значение 2, то вычисления закончены; 1-ой процессор получает корневую вершину дерева, входные данные и список ДП 1,2,..,n; когда поддерево процессора s (s=1..n) содержит вершину V с флагом 0 и списком ДП, содержащим g процессоров, включая s, тогда, начиная с i=1 и кончая i=h, где 1..h - веса ребер, исходящих из вершины V, производится параллельное вычисление поддеревьев, начинающихся со всех u(i) исходящих из V ребер веса i, у которых флаги равны нулю; если g≤u(i) то каждому процессору z из списка ДП передается по одной вершине, которая связана ребром U(i), и список ДП, состоящий из одного процессора z; если g>u(i), то список ДП делится на u(i) частей так, чтобы s был первым процессором в 9 первой части; первому процессору в j-той (j=1..u(i)) части списка ДП передается j-тая вершина из U(i) и вся j-тая часть списка ДП, если передаваемая вершина не листовая, либо только первый процессор, если передаваемая вершина является листовой; когда процессор s получил листовую вершину, которая связана входным ребром R с вершиной V, то флаг ребра R устанавливается равным 1, когда он заканчивает вычисление этой вершины, то флаг ребра R устанавливается равным 2 и номер процессора s дописывается в список ДП вершины V; когда изменяется флаг вершины, то его новое значение присваивается флагу ребра, входящему в эту вершину; если вершина V не корневая вершина дерева алгоритма, флаг вершины V не равен 0 и ее список ДП не пуст, то ее список ДП дописывается в список ДП вершины, с которой она связана входным ребром.
9. Способ вычислений на многопроцессорном кластере по п.3, отличающийся тем, что размеры частей, на которые делится список «подчиненных» процессоров, равны или отличаются не более чем на 1, при этом часть с меньшим номером не может быть меньше части с большим номером.
10. Способ вычислений на многопроцессорном кластере по п.8, отличающийся тем, что размеры частей, на которые делится список дополнительных процессоров, равны или отличаются не более чем на 1, при этом часть с меньшим номером не может быть меньше части с большим номером.»
При экспертизе заявки по существу к рассмотрению была принята данная формула.
По результатам рассмотрения ФИПС принял решение об отказе в выдаче патента на основании того, что предложение заявителя не может быть признано относящимся к изобретениям в смысле положений Патентного закона 10 Российской Федерации от 23.09.1992 №3517-1, в редакции Федерального закона "О внесении изменений и дополнений в Патентный закон Российской Федерации " № 22 – ФЗ от 07.02.2003 (далее – Закон).
Так, в решении ФИПС отмечено, что часть признаков независимого пункта заявленной формулы известна из опубликованной 01.10.2003 заявки ЕР 1349327 (далее – [1]), при этом остальные его признаки представляют собой алгоритм, т.е. необходимы только для получения результата, не считающегося имеющим технический характер.
Заявитель в своем возражении выразил несогласие с решением ФИПС, ссылаясь на то, что экспертизой ФИПС неверно приведена ссылка на документ [1], для которого, по мнению заявителя, нехарактерны указанные в решение об отказе в выдаче патента признаки заявленной формулы изобретения.
Изучив материалы дела и заслушав участников рассмотрения возражения, коллегия палаты по патентным спорам находит доводы, изложенные в возражении, не убедительными.
С учетом даты поступления заявки правовая база для оценки охраноспособности заявленного предложения включает упомянутый выше Закон, Правила составления, подачи и рассмотрения заявки на выдачу патента на изобретение, утвержденные приказом Роспатента от 06.06.2003, зарегистрированным в Министерстве юстиции Российской Федерации 30.06.2003 № 4852 (далее – Правила ИЗ) и Правила ППС.
В соответствии с пунктом 1 статьи 4 Закона, в качестве изобретения охраняется техническое решение в любой области, относящееся к продукту (в частности, устройству, веществу, штамму микроорганизма, культуре клеток растений и животных) или способу (процессу осуществления действий над материальным объектом с помощью материальных средств).
В соответствии с пунктом 2 статьи 4 Закона (пункт 2.2.1 Правил ИЗ) не считаются изобретениями в смысле положений настоящего Закона, в частности: 11 открытия, а также научные теории и математические методы; решения, касающиеся только внешнего вида изделий и направленные на удовлетворение эстетических потребностей; правила и методы игр, интеллектуальной или хозяйственной деятельности; программы для электронных вычислительных машин; решения, заключающиеся только в представлении информации. В соответствии с настоящим пунктом исключается возможность отнесения указанных объектов к изобретениям только в случае, если заявка на выдачу патента на изобретение касается указанных объектов как таковых.
Согласно подпункту 1 пункта 2.1.2 Правил ИЗ, способом как объектом изобретения является процесс осуществления действий над материальным объектом с помощью материальных средств.
Согласно подпункту 1.1 пункта 3.2.4.3 Правил ИЗ, сущность изобретения выражается в совокупности существенных признаков, достаточной для достижения обеспечиваемого изобретением технического результата. Технический результат представляет собой характеристику технического эффекта, свойства, явления и т.п., которые могут быть получены при осуществлении (изготовлении) или использовании средства, воплощающего изобретение. Технический результат может выражаться, в частности, в снижении (повышении) коэффициента трения; в предотвращении заклинивания; снижении вибрации; в улучшении кровоснабжения органа; локализации действия лекарственного препарата, снижении его токсичности; в устранении дефектов структуры литья; в улучшении контакта рабочего органа со средой; в уменьшении искажения формы сигнала; в снижении просачивания жидкости; в улучшении смачиваемости; в предотвращении растрескивания. Полученный результат не считается имеющим технический характер, в частности, если он заключается только в получении той или иной информации и достигается только благодаря применению математического метода, программы для электронной вычислительной машины или используемого в ней алгоритма.
12
В соответствии с подпунктом 1 пункта 19.5 Правил ИЗ заявленное предложение не признается относящимся к изобретениям в смысле положений Закона, если оно обеспечивает получение только такого результата, который не является техническим или не может быть признан относящимся к средству, воплощающему изобретение.
Существо заявленного предложения выражено в приведённой выше формуле изобретения, которую палата по патентным спорам принимает к рассмотрению.
При этом проверка патентоспособности заявленного предложения показала следующее.
В результате анализа заявленного предложения установлено, что оно не относится к патентоспособному объекту изобретения – способу. Основанием для данного вывода послужили следующие обстоятельства.
Родовым понятием, отражающим назначение в соответствии с рассматриваемой формулой изобретения является "способ вычислений".
Сущность предложения заявителя заключается в определенной алгоритмизации процесса вычисления, осуществляемого параллельно несколькими связанными между собой процессорами.
Однако, если рассматривать в качестве материального объекта, над которым производятся действия указанный многопроцессорный кластер, в котором отдельные процессоры соединены коммуникационной средой, то необходимо отметить, что он как материальный объект не претерпевает каких-либо изменений в процессе реализации заявленного предложения и не испытывает воздействия со стороны каких-либо технических средств (других материальных объектов), т.е. осуществление описанных в заявленной формуле действий не приведет к изменению свойств или технических характеристик (состояния) многопроцессорного кластера.
При этом в материалах заявки не содержится сведений о других 13 технических средствах кроме многопроцессорного кластера, на которые воздействуют, или которые воздействуют в процессе предложенной последовательности действий (см. процитированный выше пункт 2.1.2 Правил ИЗ).
Невозможность отнесения предложения заявителя к объекту-способу подтверждается также отсутствием в материалах заявки сведений о результате, который может считаться имеющим технический характер.
Так в описании к заявленному предложению отмечено, что целью его применения является получение результата, заключающегося в том, что « …в системе автоматизируется распределение вычислительных блоков задачи по процессорам, выделенным для решения этой задачи, а также автоматизируется управление потоками данных, их направлением и синхронизацией».
Однако, результат, заключающийся в возможности автоматизации процесса вычисления, достигается в заявленном предложении только благодаря применению алгоритма, используемого в программе для электронной вычислительной машины (см. процитированный выше подпункт 1.1 пункта 3.2.4.3 Правил ИЗ), таким образом, он не может считаться имеющим технический характер. Следовательно, заявленное предложение не может быть признано относящимся к изобретениям как таковым (подпунктом 1 пункта 19.5 Правил ИЗ).
Что касается доводов возражения об отсутствии в решении, описанном в документе [1], каких-либо признаков заявленного предложения, то в соответствии с вышесказанным в проведении подобного анализа нет необходимости.
Таким образом, в возражении отсутствуют доводы, опровергающие вывод ФИПС о том, что заявленное предложение относится к неохраноспособным объектам.
14
В отношении доводов заявителя, изложенных в особом мнении, необходимо отметить следующее. Вопросы, касающиеся возможности отнесения заявленного предложения к техническим решениям, охраняемым в Российской Федерации патентом на изобретение, подробно рассмотрены выше. Что касается прохождения заявки формальной экспертизы с положительным результатом, то следует отметить, что проверка патентоспособности заявленных предложений, в том числе и проверка принципиальной возможности отнесения заявленных предложений к изобретениям как таковым, регламентируется разделом 19 Правил ИЗ «Экспертиза заявки по существу», а не разделом 18 Правил ИЗ «Формальная экспертиза заявки».
