автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ

ВВЕДЕНИЕ.

1. ОПРЕДЕЛЕНИЕ ОБЪЕКТА ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ.

1.1. Анализ задачи разрезания и выбор математических моделей.

1.2. Формальная постановка задачи разрезания.

1.3. Задача выбора структур данных для реализации алгоритмов декомпозиции схем.

1.4. Анализ методов решения задачи разрезания.

Выводы.

2. ПРОБЛЕМА ВЫБОРА СТРУКТУР ДАННЫХ.

2.1. Анализ структур данных и операций над ними.

2.2. Исследование операций над линейными структурами данных.

2.3. Исследование операций над древовидными и сетевыми структурами

2.4. Классификация базовых структур данных и матрица сложностей базовых операций.

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

2.6. Локально-оптимальный алгоритм выбора структур данных.

2.7. Выбор структур данных для последовательного алгоритма разрезания гиперграфа.

Выводы.

3. АЛГОРИТМЫ ДЕКОМПОЗИЦИИ СХЕМ ПО МЕТОДУ ДВОИЧНОЙ

СВЕРТКИ.

3.1. Математическая модель процесса композиции и особенности алгоритмов свертки.

3.2. Алгоритмы свертки без учета связности.

3.3. Алгоритмы свертки с учетом связности.

3.4. Сравнительный анализ полученных результатов.

3.5. Выбор структур данных.

Выводы.

4. АЛГОРИТМ ДИХОТОМИЧЕСКОГО РАЗРЕЗАНИЯ ГИПЕРГРАФА ПО МЕТОДУ ВЕТВЕЙ И ГРАНИЦ.

4.1. Математическая модель процесса дихотомического разрезания гиперграфа по методу ветвей и границ.

4.2. Доказательство применимости метода ветвей и границ для декомпозиции схем.

4.3. Схемы реализации метода ветвей и границ.

4.4. Способы формирования дерева решений.

4.5. Способы кодирования вершин дерева решений и оценка сверху их емкостной сложности.

4.6. Кодирование огибающей цепи.

4.7. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и границ.

4.8. Выбор структур данных и определение вычислительной сложности алгоритма.

Выводы.

5. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ.

5.1. Система автоматизированной декомпозиции схем.

5.2. Экспериментальное исследование вычислительной сложности алгоритмов двоичной свертки.

5.3. Исследование возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ и двоичной свертки для декомпозиции схем.

5.4. Экспериментальные исследования качественных характеристик алгоритмов.

Выводы.

Актуальность. Автоматизированное проектирование (АЛ) широко применяется при создании ЭВМ. Качество результатов конструкторского проектирования ЭВМ, т.е. технический уровень готового изделия в большой степени зависит от степени использования и возможностей систем АП. На всех этапах, начиная с эскизного проектирования и кончая выпуском конструкторской документации, решаются задачи структурного синтеза комбинаторно-оптимизационного характера. Многие из этих задач относятся к классу №>-полных [3,10,16,17,19,20,22,24,39]. В связи с этим, актуальным является разработка высокопроизводительных алгоритмов их решения, сравнение эффективности которых возможно на основании оценок вычислительных и емкостных сложностей, а также качества результатов проектирования.

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

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

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

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

Приведенные примеры говорят о высокой актуальности темы данной диссертации.

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

Очевидно, что разработка эффективных алгоритмов невозможна без исследования вариантов его конечной реализации, т.е. выбора структур данных. Вычислительная сложность вариантов алгоритма при использовании различных структур может различаться на несколько порядков. Данная задача, т.е. оптимизация выбора структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. Пути ее формализации частично рассматривается в многочисленных работах [1,2,5,8,9,10,37,42], однако ее четкой формальной постановки до сих пор не получено. Это во многом связано с разнообразием стоящих перед исследователями задач. В данной работе предпринята попытка формальной постановки задачи выбора структур данных для указанного класса комбинаторно-оптимизационных задач структурного синтеза, предложены методы ее решения, которые успешно воплощены для разработанных и исследованных алгоритмов декомпозиции схем соединения элементов ЭВМ.

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

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

Задачи исследований. Для достижения поставленных целей потребовалось:

1.Выявить перспективные методы решения задачи разрезания схем.

2.Разработать математические модели процессов разрезания схем выбранными методами.

3 .Исследовать способы снижения вычислительной и емкостной сложности реализаций выбранных методов.

4.Разработать аналитические средства оценки алгоритмов декомпозиции схем различной степени интеграции.

5.Создать алгоритмы декомпозиции и экспериментально исследовать области их применения.

Методы исследований. При решении задач данной диссертационной работы были использованы: методы теории графов, методы решения задач комбинаторной оптимизации (метод ветвей и границ, поиска в глубину, двоичной свертки); методы комбинаторного анализа, математического анализа.

Научная новизна работы.

1. Разработаны математические модели процесса декомпозиции по методам двоичной свертки и ветвей и границ, позволившие создать высокопроизводительные алгоритмы их реализации.

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

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

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

5. Исследование вариантов реализации метода двоичной свертки для решения задачи разрезания гиперграфа и проведенный выбор структур данных позволили существенно сократить вычислительную сложность алгоритма.

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

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

Апробация работы. Основные положения диссертационной работы обсуждены на Межвузовской юбилейной научно-технической конференции "Современные информационные технологии" (г. Москва 2001), Межвузовской научно-технической конференции "Современные информационные технологии" (г. Москва 2002).

Реализация и внедрения. Теоретические и практические результаты работы, полученные автором, нашли применение при разработке архитектуры и организации цифровой вычислительной системы для обработки сигналов и управления бортовым фурье-спектромётром высокого разрешения, выполняемой в рамках проекта ОКР «Метеор-М-ИКФС-2-МГТУ» и при анализе предприятия ОАО "АВТОТОР ХОЛДИНГ". Документы, подтверждающие внедрение, приведены в приложении.

Публикации. По результатам диссертационной работы автором опубликовано 4 работы.

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, занимающих 176 страниц текста, в том числе 51 рисунок и 20 таблиц, список литературы из 63 наименований на 7 страницах, приложение на 2-х листах.

Выводы

1. Проведенное экспериментальное исследование алгоритмов двоичной свертки подтвердило линейный характер их вычислительной сложности.

2. Исследование возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ для декомпозиции схем показало, что предварительное упорядочивание вершин и использование отсекающей оценки сокращает количество рассматриваемых вершин дерева решений на -30%.

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

4. Экспериментальные исследования качества решений алгоритмов показало, что точность решения, обеспечиваемая последовательным алгоритом и алгоритмом двоичной свертки составляют -90%. При этом, последовательный алгоритм позволяет с малой .скрытой константой выполнять декомпозицию на произвольное число кусков, в то время как алгоритм двоичной свертки с ограничениями на размеры кусков получает наилучший результат при разделении схемы на два куска. В подтверждение этого, в ходе экспериментов последовательный алгоритм показывал более стабильное качество результатов. Т.е. можно констатировать большую универсальность последовательного алгоритма по сравнению с двоичной сверткой при практически идентичных характеристиках точности решения.

ЗАКЛЮЧЕНИЕ

1. Разработаны математические модели процесса разрезания гиперграфа по методам двоичной свертки и ветвей и границ, что дало возможность создать алгоритмы их реализации.

2. Проведенный анализ комбинаторно-оптимизационных алгоритмов выявил совокупность операций при преобразовании исходной модели в модель результата и позволил определить сложности их реализаций для различных структур данных.

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

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

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

6. Исследование вариантов реализации метода двоичной свертки для решения задачи разрезания гиперграфа и проведенный выбор структур данных дали возможность значительно сократить вычислительную сложность алгоритма.

7. Разработан рабочий модуль, реализующий алгоритм двоичной свертки, обладающий малой вычислительной сложностью. Экспериментально исследованные характеристики его работы подтвердили правильность теоретических расчетов вычислительной сложности алгоритма.

8. Разработана модификация метода ветвей и границ для решения задачи разрезания гиперграфа, выбраны структуры данных, обеспечивающие минимальную вычислительную сложность построения одной вершины дерева решений. Определены точные размеры дерева решений. Создан алгоритм разрезания гиперграфа по методу ветвей и границ, получены оценки сверху времени работы алгоритма.

9. Разработан рабочий модуль, реализующий алгоритм разрезания гиперграфа по методу ветвей и границ. Экспериментально исследованы характеристики его работы.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

2. Ахо A.B., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы,- М.: Мир, 2000. 384.

3. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств.-Львов: Вища школа, 1981. 168 с.

4. Балдин Е.В., Шашкин Л.О. Генетические алгоритмы: возможности и ограничения // НТИ. Сер. 2. Информационные процессы и системы. 2000. - N8. - С. 19-33.

5. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. М.: Мир, 1975.-406 с.

6. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. Основы информатики: Пер. с англ. М.: Мир, 1998. - 703 с.

7. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. -'368 с.

8. Кнут Д. Искусство программирования. Т. 1.: Основные алгоритмы. 2-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2001. - 720 с.

9. Кнут Д. Искусство программирования. Т. 3.: Сортировка и поиск. 2-е изд.: Пер. с англ.: Уч. пос. М.: Издательский дом "Вильяме", 2000. - 823 с.

10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960с.

11. Кофман А. Введение в прикладую комбинаторику. М.: Мир, 1981. -480 с.

12. Кузнецов О.П., Адельсон Вельский Г.М. Дискретная математика для инженера. 2-е изд. перераб. и доп. - М.: Энергоатомиздат, 1988.-480с.

13. Курейчик В.В. Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС: Дис. кандтехн. наук. Таганрог, 1995. - 152 с.

14. Курейчик В.М. Генетические алгоритмы. Обзор и состояние // Новости искусственного интеллекта. 1998. - N3. - С. 14-63.

15. Маиника Е. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.-323 с.

16. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 303 с.

17. Методы разбиения схем РЭА на конструктивно законченные части XK.K.-Морозов, А.Н. Мелихов и др.; под ред. К.К. Морозова М.: Сов. радио, 1978. - 136 с.

18. Мину М. Математическое программирование. Теория и алгоритмы. -М.: Наука, 1990.-488 с.

19. Морозов К.К., Одиноков В.Г., Курейчик А.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983. - 280 с.

20. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. -Новосибирск: Наука. Сиб. отделение, 1990. 515 с.

21. Новые педагогические и информационные техгологии в системе образования / уч. пособ. для студ. пед. вузов; под ред. Е.С. Полат. -М.: Издательски центр "Академия", 1999. 224 с.

22. Норенков И.П., Маничев В.Б. Основы теории и проектирования САПР.-М.: Высш. шк„ 1989. 334 с.

23. Норенков И.П. Разработка систем автоматизированного проектирования: Учебник для вузов. М.: Изд-во МГТУ им. Н.Э.1. Баумана. 1994. - 207 с.

24. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. М.: Изд-во МГТУ им. Баумана, 2001. - 288 с.

25. Овчинников В.А. Вычислительная сложность алгоритмических моделей задач идентификации и покрытия схем ЭВМ // Вестник Московского государственного технического университета. Приборостроение. 1992. - N2. - С.31-42.

26. Овчинников В.А. Вычислительная сложность методов решения задачи компоновки схем ЭВМ // Вестник МГТУ им. Баумана. Приборостроение. Специальный выпуск "Системы автоматизированного проектирования". 1991. - N.2. - С.81-88.

27. Овчинников В.А. Разработка научных основ автоматизированной компоновки схем ЭВМ: Дисс. д-ра техн. наук. М.: 1986. - 380 с.

28. Овчинников В.А., Иванова Г.С., Попов А.Ю. Применение метода ветвей и границ для решения задачи дихотомического разрезания гиперграфа // Вестник Московского государственного технического университета. Приборостроение. 1999. - N2. - С.78-91.

29. Овчинников В.А., Николаев К.В., Попов А.Ю. Исследование вычислительной сложности алгоритмов двоичной свертки схем ЭВМ // Вестник Московского государственного технического университета. Приборостроение. 1997. - N2. - С. 113-120.

30. Овчинников В.А., Ратавнин В.Ю. Вычислительная и емкостная сложность свертки схем ЭВМ и корректировки их моделей // Вестник Московского Государственного Технического Университета. Приборостроение. 1994. - N2. - С.50-61.

31. Ope О. Теория графов. М.: Наука, 1980. - 336 с.

32. Орехова P.A., Дармахеев В.П., Бордоева А.Е. Математическоепрограммирование. Иркутск: Издательство Иркутского Университета, 1992. - 296 с.

33. Панадимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

34. Петрушинский В.В. Автоматизированные системы интенсивного обучения. М.: Высш. шк., 1987. - 192 с.

35. Попов А.Ю. Проблема выбора структур данных в задачах схемно-топологического проектирования. // Современные информационные технологии, Юбилейный сборник трудов кафедры. -М.: Изд-во МГТУ им Баумана, 2002. С. 57-60.

36. Райли Д. Абстракция и структуры данных: Вводный курс: Пер. с англ. М.: Мир, 1993. - 752 с.

37. Рейнголд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

38. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: Учеб. для вузов по спец. "Выч. маш., компл., сист. и сети". 2-е изд., перераб. и доп. М.: Высш. шк., 1989. - 312с.

39. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980.-276 с.

40. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. М.: ФИЗМАТЛИТ, 2002. - 240 с.

41. Трамбле Ж., Соренсон П. Введение в струткуры данных: Пер. В.И. Бриккер и др. Под ред. А.Е. Костина, В.Ф. Шаньгина. М.: Машиностроение, 1982. - 784 с.

42. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 255 с.

43. Корбут А.А., Финкелынтейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969.-368 с.

44. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2002. - 304 с.

45. Beame P., Cook S., Edmonds J., Impagliazzo R., Pitassi, T. The Relative Complexity of NP Search Problems // Journal of Computer and System Sciences. 1998. - No. 57. - P. 3-19.

46. Carpenter Т., Cosares S., Ganley J.L., Saniee I. A Simple Approximation Algorithm for Two Problems in Circuit Design // IEEE Transaction on Computers. 1998. - Vol. 47, No. 11. - P. 1240-1252.

47. Cho J.-D., Raje S., Sarrafzadeh M. Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Co.lor Ordering for VLSI Application // IEEE Transaction on Computers. 1998. - Vol. 47, No. 11. - P. 12531266.

48. Diaconis P., Saloff-Coste L. What Do We Know about the Metropolis Algorithm? // Journal of Computer and System Sciences. 1998. - No. 57. - P. 20-36.

49. Kleinberg J., Tardos E. Approximation for the Disjoint Paths Problem in High-Diameter Planar Networks // Journal of Computer and System Sciences. 1998. - No. 57. - P. 61-73.

50. Miltersen P.B., Nisan N., Safra.Sh., Wigderson A. On Data Structures and Asymmetric Communication Complexity // Journal of Computer and System Sciences. 1998. - No. 57. - P. 37-49

51. Oliveira A.L., Carloni L.P., Villa Т., Sangiovanni-Vincentelli A.L.

52. Exact Minimization of Binary Decision Diagrams Using Implicit Techniques // IEEE Transaction on Computers. 1998. - Vol. 47, No. 11. - P. 1282-1296.

53. Papakostas A., Tollis I. Interactive Orthogonal Graph Drawing // IEEE Transaction on Computers. 1998. - Vol. 47, No. 11. - P. 1267-1275.

54. Choi I.-S., Kim H„ Lim I.-Sh., Hwang S.-Y., Lee Bh.-Ch., Kim B.-T. A Kernel-Based Partitioning Algorithm for Low Power, Low-Area Overhead Circuit Design Using Don't-Care Sets // ETRI Journal. -2002. Vol. 24, No. 6. - P.473-476.

55. Michelena N., Papalambros P. A hypegraph framework for optimal model-based decomposition of design problems // Computational Optimization and Applications. 1997. - Vol. 8, No. 2. - P. 173-196.

56. Huang D.J., Kahng A.B. Partitioning-Based Standard Cell Global Placement with an Exact Objective // Proc. ACM/IEEE International Symposium on Physical Design. 1997 . - P. 18-25.

57. Eem C.-K., Chong J. An Efficient Iterative Improvement Technique for VLSI Circuit Partitioning Using Hybrid Bucket Structures // Proc. Asia and South Pacific Design Automation Conf. 1999. - P.73-76.

58. Caldwell A.E., Kahng A.B., Markov I.L. Hypergraph Partitioning With Fixed Vertices // Proc. ACM/IEEE Design Automation Conf. 1999. -P. 355-360.

59. Alpert C.J., Kahng A.B. Recent Directions in Netlist Partitioning: A Survey//Integration. 1995. - No. 19. - P. 1-81.

60. Alpert C.J., Huang J.-H., Kahng A.B. Multilevel Circuit Partitioning // ACM/IEEE Design Automation Conf. 1997. - P.530-533.

61. Karypis G., Aggarwal R., Kumar V., Shekhar S. Multilevel Hypergraph Partitioning: Applications in VLSI Design // Proc. ACM/IEEE Design Automation Conf. 1997. - P. 526-529.

62. Karypis G., Kumar V. Multilevel k-way Hypergraph Partitioning // Proe. ACM/IEEE Design Automation Conf. 1999. - P. 343-348.

63. Wichlund S., Aas E.J. On Multilevel Circuit Partitioning // Proc. IEEE International Conf. on Computer Aided Design. 1998. - P. 505-51 1.