Диссертация (1137145), страница 17
Текст из файла (страница 17)
В сущности (на практике) этот механизм позволяет создаватьмножество заданий, описывая их в форме реализации метода callинтерфейса Callable в ходящего в состав пакета java.util.concurrent. Вданном случае в качестве заданий выступает поиск одного элемента измножества запросов, оформленного в виде внутреннего статическогокласса MyCallable. Внутри метода call у объекта, который представляеттестируемую структуру данных, вызывается метод поиска и подсчитываетколичество правильно найденных k-ближайших элементов т.е. сколькосреди элементов возвращенных процедурой поиска, есть во множествеэталонных.119@Overridepublic TestResult call() throws Exception {SearchResult result = db.knnSearch(testQ, k, attempts);int good=0;for (EvaluatedElement ee: result.getViewedList())if (answer.contains(ee)) good++;return new TestResult(good, result.getViewedList().size(),result.getViewedList().size(), result.getVisitedSet());}Внутри основного кода задания создаются как объекты-экземпляры классаMyCallable, различающиеся только одним параметром – элементом докоторого производится поиск, более кратко – запросом.Обработка заданий в многопоточном режиме происходит с помощьюexecuterTreadPool, в котором скрыто взаимодействие с операционнойсистемой.Задания помещаются в executerTreadPool спомощью метода submit.
Методsubmit в ответ возвращает фьючерсы (объекты типа Future), объектыкоторые служат своего-рода семафорами для исполнения основного трэда.У каждого объекта типа Future есть методget(), исполнение которогозавершится только после того, как обработка задачи связанной сфьючерсом завершится. Это позволяет построить модель отложенныхвычислений.После того, как все задачи были загружены в executerTreadPool,исполнение основного потока (трэда) останавливается, до тех пор пока всезапущенные задачи не завершатся, что эквивалентно тому, что у всехфьючерсов, не станут известны результаты вычислений, то есть пока незавершит работу метод get у каждого фьючерса.120for (Future<TestResult> future : searchResultList) {try {TestResult tr = future.get();good += tr.getRightResutls();scanned+=tr.getScannedNumber();} catch (InterruptedException e) {throw new Error(e);} catch (ExecutionException e) {throw new Error(e);}}executor.shutdown();Так параллельно происходит подсчёт общего количества правильнонайденных ближайших соседей.
После чего вычисляется значенияточности recall (результаты экспериментов приведены в главе 3).5.10 Многопоточная реализация экспериментов с точками dмерного Евклидова пространстваВычислительный эксперимент, в ходе которого было полученораспределениедлиныпутиалгоритмаGreedyWalkвструктуреформируемой алгоритмом K-NNSearch над множеством случайных точекd-мерногоЕвклидовапространства,производилисьспомощьюпрограммного кода располагаемого в файле CommonFeatures2.java впакете org.latna.msw.evaluation.Для снижения в эксперименте фактора случайности, сборка структурыпроизводилась несколько раз. Чтобы сократить время эксперимента, егокод был спроектирован так, чтобы независимые части эксперимента моглиисполнятьсявразныхпотоках.Параллельноевычислениебылореализовано с помощью нововведения 8-го стандарта – концепции потоковданных–стримов(англ.Stream).Даннаяконцепцияпозволяетобрабатывать поток данных в функциональном стиле, описывая процессобработки данных, как функцию принимающую на вход элемент данных ивозвращающая новый объект.
Концепция стрима инкапсулирует процесс121применения такой функции к данным. Функция к данным может бытьприменена как последовательно, так и параллельно. Чтобы та или инаяфункция была применена к каждому объекту из потока данных, она(функция) передается в качестве аргумента, в метод forEach объекта классаStream.Метод forEach в качестве аргумента принимает объекты сфункциональным интерфейсом Consumer, что позволяет описыватьпараллельный код,в теле лямда-функции непосредственно на местеаргумента метода forEach,IntStream.rangeClosed(1,maxExpNumber).parallel().forEach(expNumber -> {MetrizedSmallWorld db = new MetrizedSmallWorld();db.setNN(nn);db.setInitAttempts(initAttempts);System.out.println("Exp number: " + expNumber);EuclidianFactory ef = new EuclidianFactory(dim, dbSize);EuclidianFactory testQueryFactory = newEuclidianFactory(dim, querySetSize);ef.getElements().stream().forEach((me) -> {db.add(me);});…}Ключевым моментом является вызов метода parallel() общего для всехклассов BaseStream.
Этот метод возвращает объект класса Stream, которыйможет обрабатывать поток данных параллельно.Ранее в рамках 7-го стандарта, чтобы заставить Java-машину исполнитьнекоторый набор команд параллельно, приходилось реализовыватьпаттернstrategy,черезреализациюклассасинтерфейсомjava.util.concurrent.Callable, помещая код, который должен исполнятьсяпараллельно, в метод call. Экземпляры такого класса представляют собойоднотипные задачи, параметры, к которым передаются через конструктор,что требует написания большого количества вспомогательного кода, ненесущего никакой смысловой нагрузки.122В данном случае, код исполняемый параллельно располагается внутрилябда-функции на месте аргумента метода forEach(…). Внутри лябдафункции создается объект класса MetrizedSmallWorld объект классаEuclidianFactory.
После чего в теле этого же цикла происходитпоследовательное добавление. В каждом потоке после того, как структурабыла собрана, производится оценка параметров структуры: точность,коэффициент кластеризации, распределение степеней вершин и другиепараметры.Поскольку интересны средние значения по всем экспериментам,которые в данном случае, проводятся параллельно, результаты вычисленийдолжны каким-либо образом собираться, агрегировать. Использоватьглобальную переменную для этой цели – недопустимо, поскольку большеодного потока могут одновременно изменять её значение, что ведёт кневерным результатам вычислений. Чтобы избежать такого рода ошибокиспользуютпотокобезопасныеконтейнеры,–потокобезопасныереализации структур данных или атомарных типов данных.В текущем исполнении в качестве потокобезопасных контейнеров былииспользованы классы ConcurrentSkipListSet, AtomicLong, DoubleAdder.
Вслучае класса AtomicLong и класа DoubleAdder и всех остальных классовиз пакета java.util.concurrent.atomic, потокобезопасность в конечном итогеобеспечиваетсяза счёт использованияинструкции процессора«Сравнение с обменом» (CAS – compare and swap) [M. Herlihy, 1991],позволяющей атомарно сравнить некоторую область памяти с некоторымзначением, и в случае совпадения, записать в эту область другое значение,которое также является одним из параметров команды.
Под атомарностьюпонимается, что между операциями сравнения значения области памяти счислом и записью значения в память, никакой другой поток не произведетзапись какого-либо другого значения.обуславливаетсяфизическимиАтомарностьсвойствамиинструкции CASустройствапроцессоров,поддерживающую данную команду (как правило на аппаратном уровне это123реализуется с помощью блокировки процессором шины обмена данных спамятью) [M. Herlihy, 1991].5.11 ВыводыВ главе были рассмотрены детали реализации и нюансы архитектурыклассов программной платформы с помощью, которой была полученачасть результатов. Не смотря на то, что данная программная платформарассчитана на работу только в рамках оперативной памяти одногокомпьютера, она позволяет моделировать работу алгоритмов в условияхраспределенного оборудования.Припроектированиииспользовалисьшаблоныархитектурыпроектированияпрограммнойтакиекакплатформы“Стратегия”,“Абстрактная Фабрика”.
Применение шаблонов проектирования позволилоизбежать дублирования кода тестирующего различные комбинацииалгоритмов для различных метрических пространств.Отсутствие сильной связанности между различными логическимичастями системы и достаточная степень функциональной изоляциипозволила производить вычислительные эксперименты в многопоточномрежиме.124ЗаключениеНастоящая работа посвящена алгоритмам построения распределенныххранилищ данных основанных на использовании сетевых структур иалгоритмам поиска в них.Основными результатами работы являются:1.Предложены алгоритмы организации данных в виде графаMSWConstruction, ConstructionByReparing, отличающиеся главнымобразом от ранее известных алгоритмов тем, что предложенныеалгоритмы не используют векторное представление данных2.Предложеналгоритмприближённогопоискаk-ближайшихсоседей K-NNSearch, основанного на идее жадного направленногопоиска и поиске с запретами3.Исследование свойств графов формируемых предложеннымиалгоритмаминаднекоторымиконечнымиподмножествамиметрического пространства показало, что при определённыхпараметрах, предложенные алгоритмы позволяют строить графысо свойствами навигационного тесного мира4.Былоустановлено,чтоданныеграфымогутэффективноиспользоваться для поиска k ближайших соседей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
