EduTranslator

Научные работы со всего мира

Рубрика: IT технологии (стр. 1 из 2)

SWIFT

Оригинал статьи представлен по ссылке.

Пакет программ интеграции Солнечной системы

Пакет функций SWIFT, написанный Хэлом Левисоном (Hal Levison) и Мартином Дунканом (Martin Duncan), предназначен для интеграции набора взаимно гравитационно взаимодействующих тел вместе с группой тестовых частиц, которые чувствуют гравитационное влияние массивных тел, но не влияют друг на друга или массивные тела. Включены четыре метода интеграции:

  • Отображение Висдом-Холмана (Wisdom-Holman Mapping /WHM). Этот алгоритм был создан Джеком Висдомом (Jack Wisdom) и Мэттом Холманом (Matt Holman) (нажмите ЗДЕСЬ для справки).
  • Регуляризованный метод смешанных переменных (RMVS). Он включает близкие подходы между тестовыми частицами и планетами. Этот алгоритм был создан Хэлом Левисоном & Мартином Дунканом (нажмите здесь для справки) и основан на WHM.
  • Симплектический метод четвертого порядка T+U (TU4). Этот алгоритм был создан Джеффом Кенди (Jeff Candy) и В Розмусом (W. Rozmus). Также смотрите Мартин Дункан, Бретт Гладман и Джефф Кэнди (нажмите здесь, чтобы получить ссылку).
  • Метод Булирща-Стоера (Bulirsch-Stoer).

Пакет разработан так, чтобы вызовы к каждому из методов выглядели идентичными, и так, чтобы было легко заменить один на другой.

Вы можете получить сжатый файл tar со swift, нажав здесь. Загрузите файл swift.tar.gz в каталог, который вы будете использовать в качестве основного каталога SWIFT. Теперь вы распаковываете и извлекаете файл. Для этого нужно ввести:

tar xzvf swift.tar

Теперь продолжите, чтением README.first файла.

Мы также прописали расширение SWIFT, названное SyMBA, который всегда может интегрировать полное N-тело системы, в том числе при ближних подходах между массивными телами. Пожалуйста, напишите Хэлу Левисону, чтобы получить копию.

Существует также графический пакет, доступный для анализа результатов моделирования Swift и SyMBA. Этот пакет, который известен как SwiftVis, позволяет создавать сложные сюжеты и фильмы на лету. Кроме того, он может выполнять сложные манипуляции с данными. SwiftVis настолько мощный, что я использую его для большинства своих потребностей в планировании. Для получения дополнительной информации см. веб-сайт Марка Льюиса здесь или его страницу Wikidot здесь.

ARToolKit

ARToolKit – это библиотека программного обеспечения для создания приложений дополненной реальности (AR). Это приложения, которые включают наложение виртуальных изображений на реальный мир. Например, на изображении справа появляется трехмерный виртуальный персонаж, стоящий на реальной карте. Это видно пользователем, которые одеты в специальную гарнитуру. Когда пользователь перемещает карту, виртуальный персонаж перемещается вместе с ней и появляется как прикрепленный к реальному объекту.

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

ARToolKit использует алгоритмы компьютерного зрения для решения этой проблемы. Библиотеки отслеживания видео ARToolKit вычисляют реальное положение камеры и ориентацию относительно физических маркеров в режиме реального времени. Это позволяет легко разрабатывать широкий спектр приложений дополненной реальности. Некоторые из особенностей ARToolKit включают:

  • Одиночное отслеживание положения/ориентации камеры.
  • Код отслеживания, который использует простые черные квадраты.
  • Возможность использования любых квадратных шаблонов маркеров.
  • Легкий код калибровки камеры.
  • Достаточную скорость для AR-приложений в реальном времени.
  • Дистрибутивы SGI IRIX, Linux, MacOS и Windows.
  • Распространение с полным исходным кодом.

Полное описание функций доступно здесь.

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

ARToolKit был первоначально разработан доктором Хироказу Като (Hirokazu Kato), и его текущее развитие поддерживается лабораторией технологии человеческого интерфейса (HIT Lab) в Университете Вашингтона, HIT Lab NZ в Университете Кентербери, Новая Зеландия, и ARToolworks, Inc, Сиэтл.

Важное замечание относительно вашего права на использование ARToolKit:

ARToolKit предоставляется бесплатно для некоммерческого использования под стандартной Общественной лицензией GNU. Коммерческие лицензии для профессиональной реализации ARToolKit доступны для пользователей, для которых GPL не подходит, или которым требуется более высокий уровень поддержки, или которые требуют настройки или другой модификации с помощью специалистов. Коммерческие лицензии выдаются ARToolworks, Ink., Сиэтл, США.

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

Кількісна продуктивність системи

Оригінал статті представлений по посиланню.

Комп’ютерний системний аналіз з використанням мережевих моделей масового обслуговування

Едвард Д. Лазовска, Джон Загорян,

Г. Скотт Грем, Кеннет С. Севчік

Цей текст був опублікований у Prentice-Hall, Inc. у 1984 році. Він залишається визначальною роботою з аналітичного моделювання комп’ютерних систем. Видавець повернув авторські права авторам, які роблять матеріали доступними для перегляду або завантаження тут, у форматі Adobe Acrobat PDF (безкоштовний Acrobat reader доступний тут).

Почніть тут — найпростіший спосіб отримати доступ до книги в Інтернеті через блок Зміст з гіперпосиланнями доступний по цій ссилці.

Хочете завантажити весь текст на свій комп’ютер? Zip-файл на 21mb можна взяти тут ftp.

Зміст

Введення

І. Попередня частина

  1. Огляд моделювання мережі масового обслуговування
  2. Проведення модельного дослідження
  3. Основні закони
  4. Організація черги входів і виходів мережевої моделі

II. Загальні аналітичні техніки

  1. Обмеження продуктивності
  2. Моделі з одним робочим класом
  3. Моделі з декількома класами завдань
  4. Еквівалентність потоків та ієрархічне моделювання

III. Представлення конкретних підсистем

  1. Пам’ять
  2. Диск I / O
  3. Процесори

IV. Параметризація

  1. Діюча система
  2. Еволюційна система
  3. Пропонована система

V. Перспективи

  1. Розширені додатки
  2. Використання програмного забезпечення для моделювання мережі черг

VI. Застосування

  1. Побудова моделі з RMF даних
  2. Реалізація одного класу, точного MVA
  3. Реалізація множинного класу, точний MVA
  4. Завантаження залежних сервісних центрів

Індекс

Программное обеспечение от Тоби Дрисколл (Toby Driscoll)

Оригинал статьи доступен по ссылке.

Chebfun

Chebfun – бесплатный пакет MATLAB и проект с открытым исходным кодом. Его цель состоит в том, чтобы обеспечить численное вычисление с функциями. Мой интерес и вклад в систему наиболее заметен в решении обыкновенных и (1+1 мерных) дифференциальных уравнений в частных производных. Используя знакомый синтаксис MATLAB, такой как \ и eigs, решения краевых или собственных задач могут быть получены с полной числовой точностью автоматически.

Schwarz-Christoffel Toolbox

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

Другие программы MATLAB

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

Я написал несколько разных утилит для MATLAB:

latex

Выведите матрицу в формате, который можно вставить в среду LaTeX.

gslope

Нажмите на две точки и получите наклон между ними, вычисленный автоматически.

unplot

Удалите последние нарисованные графические объекты.

wysiwyg

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

В моей области обмена файлами MATLAB есть еще несколько утилит.

Вкладені Слова

Або Видимі магазинні мови

Оригинал статьи представлен по ссылке.

Що таке вкладені слова?

Вкладені слова — це модель представлення даних як з лінійним порядком, так і з ієрархічно вкладеним співпадінням елементів. Приклади даних з такою подвійною лінійно-ієрархічною структурою включають виконання структурованих програм, анотованих лінгвістичних даних і документів HTML / XML. Вкладене слово складається з послідовності лінійно впорядкованих позицій, доповненої полями вкладеності, що з’єднують виклики з поверненням (або відкриті теги з закритими тегами). Поля не перетинаються, створюючи правильно вкладену ієрархічну структуру, і ми дозволяємо деяким сторонам перебувати в очікуванні. Ця структура вкладеності може бути унікально представлена послідовністю, яка визначає типи позицій (виклики, повернення і внутрішні елементи). Вкладені слова узагальнюють як слова, так і впорядковані схеми, і дозволяють виконувати операції над словом і схемою.

Автомати вкладених слів – кінцеві акцептори для вкладених слів, які визначають клас регулярних мов вкладених слів. Цей клас має всі привабливі теоретичні властивості, якими володіють класичні регулярні мови слів: детерміновані вкладені автомати слів так само виразні, як і їх недетерміновані аналоги; клас закритий в об’єднанні, перетином, доповненням, конкатенацією, Кліні (Kleene -*), префіксами і гомоморфізмами мови. Членство, пустота, включення мови та еквівалентність – все це  допустимо. Визначність в монадичній логіці другого порядку точно відповідає розпізнаваності кінцевого стану. Ці результати також узагальнюються на нескінченні вкладені слова.

Як вони співвідносяться з мовами слів вільними від контексту?

При подачі мови L вкладених слів над алфавітом, лінійне кодування вкладених слів дає мову L ‘ над позначеним алфавітом, що складається з символів, позначених типом позиції. Якщо L – звичайна мова вкладених слів, то L ‘ не містить контексту. Фактично, автомат з магазинною памяттю, включаючи L’, має спеціальну структуру: при читанні виклику автомат повинен натиснути один символ, при читанні символу повернення він повинен видалити один символ (якщо стек не порожній), а при читанні внутрішнього символу він може тільки оновити стан управління. Ми називаємо такі автомати явними магазинними автоматами  (visibly pushdown automata), а клас мови слів, які вони приймають явними магазинними мовами (visibly pushdown languages VPL). Оскільки наші автомати можуть визначатись, VPL відповідають підкласу детермінованих контекстно-вільних мов (DCFL). VPL узагальнюють парантезіс (paranthesis) мов, (мов взятих в дужки), і збалансованих мов, і вони мають кращі властивості закриття, ніж CFLs, DCFLs, або мови парантезіс.

Ми стверджуємо, що для алгоритмічної перевірки структурованих програм замість того, щоб розглядати програму як контекстно-вільну мову над словами, слід розглядати її як звичайну мову вкладених слів (або, що те ж саме, видимі магазинну мову), і це дозволило б перевіряти моделі багатьох властивостей (таких як перевірка стеку, попередні умови), які не виражаються в існуючих логіках специфікацій.

В цілому, автомати магазинної пам’яті служать двом різним цілям: виявленню ієрархічного відповідності та обробці / запиту відповідності. У додатках, де актуальна тільки друга мета (як в аналізі програм), можна замінити магазинні автомати на NWA та отримати багато переваг.

Як вони ставляться до впорядкованих схем?

Дані з подвійною лінійно-ієрархічною структурою традиційно моделюються за допомогою двійкових і, в більш загальному плані, з використанням впорядкованих нерейтингових схем і запитів з використанням деревовидних автоматів. В упорядкованих схемах вузли з одним і тим же батьківським елементом лінійно впорядковані, а класичні обходи дерева, такі як інфікс (або спершу глибші зліва направо), можуть використовуватися для визначення невидиміго порядку всіх вузлів. Виявляється, хеджування, де воно є послідовністю впорядкованих схем, є особливим класом вкладених слів, а саме, тих, які відповідають словами Dyck, а регулярні мови хеджування відповідають збалансованим мовам.

Для обробки документів вкладені слова мають багато переваг перед впорядкованими схемами. Подання на основі деревовидної структури невидимі припускає, що вхідні лінійні дані можуть бути проаналізовані в схемі, і, таким чином, не можна уявити і обробити дані, які можуть бути неправильно проаналізовані. Операції Word, такі як префікси, суфікси та конкатенації, хоча і природні для обробки документів, не мають аналогічних операцій для схем. По-друге, деревовидні автомати можуть природно виражати обмеження на послідовність міток уздовж ієрархічного шляху, а також уздовж однорівневих вузлів зліва направо, але їм важко захопити обмеження, які відносяться до глобального лінійного порядку. Наприклад, запит, з паттерном p1,… pk з’являється в документі в такому порядку, компілюється в детермінований автоматон слова (і, отже, детермінований NWA) лінійного розміру, але стандартний детермінований знизу вгору деревовидний автомат для цього запиту повинен мати експоненціальний розмір k. NWA можна розглядати як свого роду деревовидні автомати, так що як нижні, так і верхні деревовидні автомати є приватними випадками. Ці результати означають, що запит може бути більш лаконічно закодований в представленні вкладених слів з перевагами складності. вкладений автомат слова читає слово зліва направо, обробляючи поля вкладеності в міру їх надходження. Це відповідає SAX API для XML і, таким чином, має природне використання в потокових алгоритмах.

Посилання

Модель вкладених слів пройшла через кілька ітерацій: див. Мови зниження Видимості; Алур і Мадхусудан; STOC 2004; і Додавання структури вкладеності у слова; Алур і Мадхусудан,; DLT 2006. Ми рекомендуємо ознайомитися з цією уніфікованою повною версією (журнал ACM, 2009). Запрошена доповідь на CSR 2007 також є хорошою відправною точкою.

Мета цієї сторінки-відстежувати великі подальші дослідження з цієї теми. Напишіть мені в коментарі та / або попозиції.

Інструменти

  • OpenNWA: бібліотека автоматів вкладених слів; Дріскол, Такур і Репс; CAV 2012.
  • Бібліотека кінцевих автоматів (Ultimate Automata Library); Хейзман, Нуц і Шилінг, 2017.

Додаткові проблеми прийняття рішень по VPA / NWA

  • Видимі магазинні ігри; Лодінг, Мадхусудан, і Серр; FSTTCS 2004.
  • Видимі магазинні автомати: від мовної еквівалентності до моделювання та бісимуляції; Сбра; CSL 2006.
  • Проблеми регулярності для видимі магазинних мов; Барані, Лодінг і Серре; STACS 2006.
  • Про проблему членства для видимі магазинних мов; Ла Торре, Napoli і Parente; ATVA 2006.
  • Символічні видимі магазинні автомати; D Antoni і Alur; CAV 2014.

Конґруенції та мінімізація

  • Конгруенції для видимі магазинних мов; Алур, Кумар, Мадхусудан і Вішванатан; ICALP 2005.
  • Мінімізація, навчання і тестування відповідності булевих програм; Кумар, Мадхусудан і Вішванатан; CONCUR 2006.
  • Мінімізують варіанти явних магазинних автоматів; Червет і Валукевич; MFCS 2007.
  • Мінімізація явних магазинних автоматів з використанням часткового Max-SAT; Хейзман, Шілінг і Тіщнер; TACAS 2017.

Тимчасова і фіксована логіка; виразність

  • Часова логіка вкладених викликів і повернень; Алур, Етессамі, Мадхусудан; TACAS 2004.
  • Регулярні мови вкладених слів: нерухомі точки, автомати і синхронізація; Arenas, Barcelo і Libkin; ICALP 2007.
  • Першопорядкові і темпоральні логіки для вкладених слів, Алур, Аренас, Барсело, Етессамі, — місіс Тіммерман, і Лібкін; LICS 2007.
  • Чергувальні автомати і тимчасове обчислення фіксованих точок для видимі магазинних мов; Bozzelli; CONCUR 2007.
  • Граматична репрезентація явних магазинних мов; баран і Барринджер; WoLLIC 2007.
  • Зважена логіка для вкладених слів і алгебраїчних формальних статечних рядів; Матіссен; ICALP 2008.
  • Помітно раціональні вирази; Боззеллі і Санчес; FSTTCS 2012.
  • Помітно лінійна тимчасова логіка; Боззеллі і Санчес; IJCAR 2014.

Специфікації для аналізу програми

  • Аспекти на основі VPA: краща підтримка AOP за протоколами; Нгуєн і Судхольт; SEFM 2006.
  • Інструментування C-програм з вкладеними словесними моніторами; Чаудхурі і Алур; SPIN 2007.
  • Синтезування моніторів для властивостей безпеки — це час з дзвінками і поверненнями; Росу, Чен, і Болл; RV 2008.
  • Тимчасові міркування для процедурних програм; Алур і Чаудхурі; VMCAI 2010.
  • Вкладені інтерполянти; Хайцманн, Хоеніке, і Поделскі; POPL 2010.
  • Перевірка сумісності виробника і споживача; Дрскол, Бартон, Репс; FSE 2011.
  • Безпечне програмування через видимі ігри магазинної безпеки; Харріс, Джа і Репс; CAV 2012.

Обробка XML і деревовидні автомати

  • Видимі магазинні ефекти виразів для обробки XML потоку; Пітчер; план-X 2005.
  • Видимі магазинні мови для потокової передачі XML; Кумар, Мадхусудан, і Вішванатан; WWW 2007.
  • З’єднання слова і схеми; Алур; стручки 2007.
  • Переписування явних магазинних мов для впровадження даних по XML; Томо і Венкатеш; CIKM 2008.
  • Потокова автоматна схема; Гаувін, Ніехрен, і Роос; Обробка інформаційних листів 2009.
  • Сама рання відповідь на запит для детермінованих вкладених автоматів слів; Гаувін, Ніехрен і Тісон; FCT 2009.
  • Автомати запитів для вкладених слів; Мадхусудан і Вішванатан; MFCS 2009.
  • Від регулярних виразів до вкладених слів: уніфікація мов і виконання запитів для реляційних і XML послідовностей; Мозафарі, Женг, Заніоло; VLDB 2010.
  • Високопродуктивна комплексна обробка подій по XML потоках; Мозафарі, Женг, Заніоло; SIGMOD 2012.
  • Стрімінгові фрагменти наступного XPath; Гаувін і Ніегрен; CIAA 2012.
  • Раннє виділення вузлів в XPath на XML-потоках; Дебарбо, Гаувін, Ніегрен, Себастьян, і Жергаві; 2012.

Перетворювачі

  • Видимі магазинні датчики для приблизної перевірки потокової передачі XML; Томо, Венкатеш і Йе; FoIKS 2008.
  • Видимі магазинні датчики; Раскін і Сервос; ICALP 2008.
  • Еквівалентність детермінованих вкладених слів словам перетворювачам; Ставорко, Лоренц, Лемей, Ніегрен; FCT 2009.
  • Властивості явних магазинних перетворювачів; Е. Філло, Ж.-Ф. Раскін, П.-А. Реньє, Ф. Серве і Ж.-М. Талбо; MFCS 2010.
  • XEvolve: Основи еволюції схеми XML; Ф. Пікалауса, Ф. Серве і Е. Жіманий ; SACSVT 2011.
  • Можливість стрімінгу вкладених слів трансдукції; Е. Філіот, О. Гаувін, П.-А. Реньє, Ф. Серве. FSTTCS 2011.
  • Потокове перетворювачі дерево; Р. Алур і Л. Д Ентоні; ICALP 2012.
  • Видимі магазинні датчики з поглядом-вперед. Е. Філіо і Ф. Серве. SOFSEM 2012.

Вкладені схеми

  • Обчислення фіксованих точок для локальних і глобальних програмних потоків; Алур, Чаудхурі і Мадхусудан; POPL 2006.
  • Мови вкладених схем; Алур, Чаудхурі і Мадхусудан; CAV 2006.
  • Видимі магазинні мови і переписування умов; Чабин і Реті; FroCos 2007.
  • Видимі деревовидні автомати з пам’яттю і обмеженнями; Комон-Лаун, Джакмар, Перрін; логічні методи в інформатиці 2008.

Слова з множинними вкладеннями

  • Примітка про вкладені слова; Бласс і Гуревич; Microsoft Research TR; 2006.
  • Надійний клас контекстно-залежних мов; Ла Торре, Мадхусудан і Парлато; LICS 2007.
  • 2-видимі магазинні автомати; Каротенуто, Мурано і Перон; DLT 2007.
  • Реалізація паралельних рекурсивних програм; Болліг, Гріндей і Габермель; FoSSaCS 2009.

Нові результати з використанням видимості викликів / повернень

  • Ідеалізований Алгол третього порядку з ітерацією дозвоів; Муравський І Валукевич; FoSSaCS 2005.
  • Синхронізація магазинних автоматів; Caucal; DLT 2006.
  • Пропозиціональна динамічна логіка з рекурсивними програмами; Лодінг і Серре; FoSSaCS 2006.
  • Високо-детерміновані магазинні автомати; Новотка і Срба; ПМП 2007.
  • Нескінченна автоматна характеристика подвійного експоненціального часу; Ла Торре, Мадхусадан і Парлато; CSL 2008.

Складна відкрита проблема (Тепер вирішена!)

Розглянемо наступне питання: дано дві регулярні мови L1 і L2 вкладених слів, існує регулярна мова R слів с позначками алфавіту, що перетину (R,L1), чи рівна вона L2? Це, як відомо, не дозволено, навіть для приватного випадку, коли L1 є безліччю всіх добре підібраних слів. Мотивація наступна: в загальному випадку, щоб перевірити, чи належить вхід L2, обробній машині потрібен стек. Але припустимо, що у нас вже є деякі додаткові знання про вході, що він належить множині L1 (наприклад, ми можемо знати, що вхід добре узгоджений), чи можуть ці знання бути використані для побудови DFA таким чином, що для входів в L1 A може вирішатися приналежність до L2. Ця проблема натхненна документом «перевірка потокових XML-документів» Сегуфіна і Віану, PODS 2002, який також представляє часткове рішення.

Нещодавно Ерік Копчинський довів невирішеність цієї проблеми: Див. Невидимі магазинні мови, LICS 2016.

CS4200 / 5200: компьютерная архитектура, Весна 2012

Оригинал статьи доступен по ссылке.

Время и Место.: MW 4: 30 – 5: 45, ENG 109

Инструктор: Д-Р Сяобо (Джо) Чжоу (Xiaobo (Joe) Zhou)

Офис: 199 Engineering

Часы работы офиса: MW 3: 00 — 4: 00

Телефон: 719-255-3493

Электронная почта: zbo@cs.uccs.edu

Программа курса: PDF

Примечания к лекции: PDF

Описание курса

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

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

Объявление

Что нового?

23 апреля: Здесь нет занятия Ср, 25 апреля. Следующий урок состоится 30 апреля.

18 апреля: доступно домашнее задание по иерархии памяти; время урока 30 апреля (понедельник). Отнесите его к памяти.

Апр 18: Напоминание: проект должен быть с демо в классе до 2 мая (ср); обратитесь к HTML-версии для деталей. Вы должны убедиться, что симулятор работает на вашем ноутбуке.

30 марта: Доступно домашнее задание по конвейеризации; Время урока 9 апреля (понедельник). Он находится на конвейере.

19 марта: Результаты промежуточного экзамена были опубликованы в сегодняшнем классе. Если вы пропустили сегодняшнее занятие, приходите ко мне в офис, чтобы забрать свой промежуточный результат. Есть также некоторые ранжированные домашние задания, которые можно взять в моем кабинете (я выпустил их для класса, но не взял). Пожалуйста, сделайте это как можно скорее.

22 февраля: доступно домашнее задание по Datapath; Из-за времени занятия 29 февраля. Обратитесь его к Datapath.

22 февраля: обратите внимание, что домашнее задание по чтению, которое я должен выполнить, продлено до Понедельника 5 марта, времени занятий.

13 февраля: доступно домашнее задание по ISA; до 20 февраля время занятий (Понедельник); обратитесь к ISA.

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

3 января: учебник, учебный план, конспекты лекций информация доступна.

Чтение и задания по проекту

Чтение Задание 1: Чтение-1, к дате 29 февраля и времени занятий.

Проект: HTML; до среды, 2 мая, время занятия (демо можно ожидать в лаборатории или на ваших собственных ноутбуках).

Необходимые основная информация

Обязательное условие: CS2160 «Компьютерная организация и ассемблерное программирование» или эквиваленты.

Знание языка высокого уровня (C / C++, Java или c# — хорошая альтернатива) и структуры данных.

Понимание программирования на языке ассемблера (MIPS и / или IBM PC): опкоды, операнды и т.д.

Если вы хотите посетить занятия без этого бекграунда, вы должны получить разрешение от инструктора.

Учебник

Требуется: Дж. Л. Хеннесси и Д. A. Паттерсон,»Компьютерная архитектура: количественный подход», Морган Кауфман, 5-е издание (2011). Текст может быть дополнен некоторыми дополнительными заданиями по чтению.

Справка (и обязательно): Д. А. Паттерсон и Дж. Л. Хеннесси «Компьютерная организация и дизайн: аппаратно-программный интерфейс», Морган Кауфман, 4-е издание (2008). Я надеюсь, что инструкторы CS2160 сказали вам, что книга необходима для CS4200 / 5200. Некоторые материалы представлены в справочнике, но конспекты лекций и слайды являются самодостаточными.

Цели курса и предварительное расписание

  • Введение в компьютерную архитектуру (1-2 лекция)
  • Количественная оценка эффективности проектирования (3 лекции)
  • Архитектуры наборов инструкций MIPS (1 лекция)
  • Принципы и примеры набора инструкций (2 лекции)
  • Дизайн-процесс: пути данных и блок управления (2-3 лекции)
  • Конвейерная передача данных и управление (2-3 лекции)
  • Опасности трубопроводов (2-3 лекции)
  • Параллелизм на уровне инструкций (2 лекции)
  • Подсистемы памяти: кэш (6 лекций)
  • Подсистемы памяти: Виртуальная память (1-2 лекции)
  • Подсистемы ввода / вывода: взаимодействие ввода / вывода с ЦП (2-3 лекции)
  • Виртуализация серверов и центров обработки данных (1-2 лекции)

Расписание Экзаменов

  • Промежуточный экзамен запланированный: 4: 30 вечера — 5: 45 вечера, Ср, 7 марта 2012 года; в классе; без пересдачи.
  • Выпускной экзамен (FIRM): 4:30 вечера-7: 00 вечера, ср, 9 мая 2012 года; в классе; без пересдачи.
  • Все экзамены с закрытыми книгами и тетрадями. Однако разрешается иметь при себе один двусторонний лист справки размером 8,5 на 11 дюймов.
  • Пример в формате PDF только говорит вам, что это основной формат и стиль экзаменов, ничего не связано с содержанием.
  • Лучший способ подготовки к экзаменам – это повторить примеры из лекций и домашних заданий, просмотреть учебник по лекциях, и, конечно, посещать все лекции.
  • Если вы планируете другой экзамен, который пересекается с этими экзаменами, вам необходимо договориться с другим преподавателем, чтобы сдать этот экзамен в другое время.
  • В случае каких-либо изменений, это будет объявлено в классе и на веб-сайте курса за 1-2 недели до изменения.

Шкала Оценивания

Процент — Оценка

[90, 100] A

[87, 90] A-

[84, 87] B+

[80, 84] B

[75, 80] C+

[70, 75] C

[65, 70] D+

[60, 64] D

Ниже 60 F

Пограничные случаи будут решаться участием студентов в классе, предоставляя интеллектуальные вопросы, информативные комментарии и конструктивную критику.

Процент оценивания

Бакалавриат (CS4200) — магистратура (CS5200)

Дисциплина и посещаемость: 4% — Дисциплина и посещаемость: 4%

Домашнее Задание: 20% — Домашнее Задание: 20%

Проект и чтения: 20% — Проект и чтения: 20%

Промежуточный экзамен: 20% — Промежуточный экзамен: 20%

Выпускной Экзамен: 36% — Выпускной Экзамен: 36%

Все экзамены будут оцениваться самим экзаменатором.

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

Будет один трехнедельный проект с использованием C / C++. Для участников CS5200 проект необходимо выполнять индивидуально. Участники CS4200 должны выполнять проект в командах; товарищи по команде могут быть назначены инструктором (на основе случайного выбора) до выпуска проекта. Проект заключается в изучении небольшого расширения концепции, которую мы изучаем на занятиях, или в проверке экспериментальных данных в какой-либо статье. Более подробная информация о проекте будет доступна по ходу семестра.

Стратегия курса

Последний день без специального разрешения декана: 30 марта 2012 года

Если у вас есть инвалидность, для которой вы запрашиваете жилье, вам рекомендуется связаться с Бюро по делам инвалидов в течение первой недели занятий. Офис по обслуживанию инвалидов расположен в главном зале № 105. (Телефон: 255-3354)

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

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

Позднее домашнее задание, чтение и представление проекта: теряет 30% своей стоимости в день, за исключением крайних неакадемических обстоятельств, таких как болезнь. В таких случаях необходимо предоставить достаточные и убедительные доказательства, т. е. справки от врачей.

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

Соблюдение Этического кодекса университета будет строго контролироваться и соблюдаться. Это будет касаться заданий, проектов и экзаменов.

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

Любая работа, представленная на оценку, должна включать следующее заявление и быть подписана и датирована. Если это отсутствует или не подписано и датировано, работа будет возвращена без оценки.

Ссылки на сайты Компьютерной архитектуры и обеспечения информации

Ссылка на «Архитектура ЭВМ»

Ссылка на «Компьютерная организация и дизайн: аппаратно-программный интерфейс»

Ссылка на «Компьютерная архитектура: количественный подход»

Ссылка на Комитет по оценке эффективности систем

Ссылка на Совет по обработке транзакций

Ссылка на Агентство национальной безопасности

Ссылка на NIST, отдел компьютерной безопасности, Центр ресурсов компьютерной безопасности

Ссылка на Общие критерии оценки информационной безопасности

Ссылка на Министерство внутренней безопасности США

Ссылка на МСЭ (Международный союз электросвязи

Ссылка Общество Интернета (ISOC)

Ссылка на Инженерную целевую группу по интернету (IETF)

Ссылка на Совет по архитектуре интернета (IAB)

Ссылка на Международную Организацию по стандартизации (ИСО)

Ссылка на Компьютерное общество IEEE

Ссылка на Ассоциацию вычислительной техники (ACM)

Ссылка на USENIX: Ассоциация передовых вычислительных систем

Получение NVSS данных по FTP

Оригинал статьи под авторством Jim Condon доступен по ссылке.

Большие (4 X 4 градусов) карты и связанные с ними наборы данных с несколькими источниками (u,v) хранятся в виде двоичных файлов в формате FITS. Карты хранятся в сжатом виде gzip, но можно запросить несжатую форму (см. ниже). Каждая карта названа прямым восхождением J2000 и склонением ее центра, а первая буква указывает плоскость (плоскости) поляризации. Например, C2230P84.gz – это картографический куб с плоскостями Стокса I, Q и U, центрированный по правому восхождению = 22h 30m, склонению = +84 градусов. I0224M32.gz содержит только плоскость полной интенсивности, центрированную по правому восхождению 02ч. 24м., склонение -32 град. Соответствующий файл данных с несколькими источниками (u,v) называется J0224-32.MS. Сжатые кубы карт имеют размер около 1,7 мегабайт, а карты общей интенсивности меньше (около 0,7 мегабайт) для более быстрого доступа пользователей, не заинтересованных в линейной поляризации. Файл paper.ps (около 4,7 Мб) содержит подробное описание NVSS. Этот документ был опубликован; источником является публикация Кондон, Дж. Дж., Коттон, У. Д., Грейзен, Е. В., Инь, Ф. В., Перли, А. Р. Тейлор, Г. Б., а также Бродерик, Дж. Дж. (Condon, J. J., Cotton, W. D., Greisen, E. W., Yin, Q. F., Perley, R. A., Taylor, G. B., & Broderick, J. J. 1998, AJ, 115, 1693).

Пример анонимного сеанса FTP показан ниже:

ftp nvss.cv.nrao.edu

login: anonymous

password: (type your full email address here)

cd pub/nvss (to access the NVSS public directory)

ls (to list the directory contents)

get paper.ps (to get a postscript copy of the paper)

binary (to copy binary files)

cd MAPS (to access the MAPS directory)

get C2230P84.gz (to get the compressed map cube centered on 22h 30m, +84 deg)

get I0224M32 (to get the total-intensity map centered on 02h 24m, -32 deg in uncompressed form)

cd ../CATALOG (to go to the CATALOG directory)

get CATALOG.FIT (to get the source catalog as a FITS binary table)

quit

Сжатие: изображения хранятся как стандартные файлы FITS, сжатые в формате GNU zip (gzip). Расширение gz, обозначает сжатие. Если требуется несжатая версия, опустите .gz при запросе файла. Gzipped файлы могут быть распакованы с помощью команды gunzip, которая доступна для большинства компьютерных систем. См. текстовый файл pub/nvss/compress.txt для более подробного описания gzip.

Румынский перевод этой страницы был предоставлен Web Geek Science.

Кодирование на основе мультипроектора

Оригинал статьи под авторством Dr. Michael S. Brown.

Обзор

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

Кому следует использовать этот код

Новичкам, кто хочет построить свою собственную систему дисплея для камеры-проектора; они могут использовать этот код как начальную отправную точку
Ученым которые заинтересованы в системе дисплея для камеры-проектора; они могут использовать этот код в качестве cсылки.

Архитектура системы

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

Изображение Архитектуры Системы
Схема 1. архитектура системы нашего мультипроекторного дисплея созданного на основе PC кластера.

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

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

Вы можете найти больше информации о геометрической центровке из Главы 3 ссылки [1], про цветовую целостность из Главы 4 ссылки [1], про рендеринг на основе PC-Кластера из Главы 5 ссылки [1]. Очень рекомендуем вам тщательно изучить всю книгу перед началом работы над своим мультипроекторным дисплеем. 

Требования к аппаратуре и программному обеспечению 

Для того чтобы использовать указанные коды вам надо обеспечить такие требования к аппаратуре и программному обеспечению:

Требования к аппаратуре:

Один PC с мониторами, в качестве главного PC;
два или больше PC с соответствующими графическими картами (мы используем NVIDIA GeForce 8800GTS), в качестве рендеринговых PC;
Два или более проектора (один на каждый рендеринговый PC);
Один хаб или роутер и сетевые кабели;
Одна OpenCV-совместимая камера с подходящими линзами  (смотрите see FAQ для более подробной информации о том как выбрать камеру и линзы.);

Требования к программному обеспечению:

Windows XP установленный на всех PC;

(Ниже указаны дополнительные программы которые надо установить в случае если вы хотите скомпилировать исходные коды сами)
Microsoft Visual Studio 2005 или версия новее;
OpenCV library 1.0 (из ссылки [2]) installed;
GLUT library 3.7 (из ссылки [3]) installed;
FreeImage Algorithms (из ссылки [4]) installed;

Ссылки

[1] «практический мультипроектный Дизайн Дисплея», Majumder/Brown, AK Peters, США, 2007
[2] Open Computer Vision Library, 1.0: http://sourceforge.net/projects/opencvlibrary/
[3] GLUT — The OpenGL Utility Toolkit, 3.7: http://www.opengl.org/resources/libraries/glut/
[4] FreeImage Algorithms Library: https://code.launchpad.net/~glennpierce/+junk/main

Противоядие компьютерному мышлению

Оригинал статьи под авторством Valdemar W.Setzer доступен по ссылке.

Компьютеры – это абстрактные машины. Другое, конкретное, машины преобразуют, транспортируют или хранят энергию, или материю. Компьютеры делают это с данными. Я охарактеризую здесь «данные» как фрагменты определенных видов информации, которые могут быть вставлены в компьютер. Данные и информация не являются частью естественного или искусственного мира, они не являются конкретными – они не могут быть взвешены, пространственно измерены, они не могут быть приняты в пищу или использованы для одежды. Мы даже не можем построить компьютер с ними. Это связано с тем, что данные и информация – на самом деле мысли. Мы думаем о них, а затем вставляем их в компьютер. То же самое относится и к программам, которые также являются частями данных.

Каждая команда или инструкция программы является результатом чистого мышления. То, что делает компьютер, когда он интерпретирует программу («выполнение программы» не является правильным выражением), заключается в том, чтобы имитировать именно те мысли, которые мы имели, когда мы вставляли их в программу. Давая программе входные данные, результат ее интерпретации компьютером может быть смоделирован мысленно или карандашом и бумагой (я пренебрегаю здесь компьютером, управляющим другими машинами, как в токарном станке с числовым управлением; я также не рассматриваю временные ограничения или ошибки, сделанные человеком). Это не так с другими машинами: имитация велосипеда с карандашом и бумагой не перенесет меня отсюда туда. Компьютеры нельзя использовать в качестве транспортных средств, их результат нельзя использовать в качестве еды или одежды, они не производят ничего реального: они производят ограниченные виды мыслей – данных. Таким образом, компьютеры полностью отчуждены от «реальности» (в наивном смысле) — это абстрактные, математические, логико-символические машины.

Что же делает программист? Чтобы создать программу, он должен мыслить совершенно особым образом, используя совершенно особый язык. Этот язык абсолютно формален: он выражается через логико-символические элементы, может быть полностью описан в математических терминах, используя то, что называется «формальной грамматикой» и «формальной семантикой». Последнее –  неправильное название, потому что за командами или инструкциями программы нет смысла, присвоенного «реальному миру». Смысл заключается в логической интерпретации инструкции. На самом деле, компьютер имеет еще одну характеристику, которую следует добавить к предыдущему абзацу: это синтаксическая машина. Каждая часть данных или программы должна быть преобразована в чистую структуру, которая будет представлена в машине. (Кстати, я считаю математическую логику чисто синтаксической, и логики подтвердили это впечатление.) Поэтому бедный программист вынужден думать очень узко, выясняя, как выразить через инструкции преобразование данных, которое он должен приказать выполнить компьютеру.

Я хотел бы упомянуть здесь пример, который уже довольно стар, из компьютерной лингвистики. Когда-то давно, в 60-е годы, некоторые лингвисты решили использовать компьютер, чтобы обнаружить литературные стили или характеристики каждого автора. Они уменьшили стиль до определенных числовых или статистических свойств, например, сколько раз в тексте появлялись такие слова, как «война», «Мир», «любовь». Они также считали «расстояние» в количестве слов, которые появились между парами ключевых слов, как эти три, и так далее. Очевидно, что они не использовали в качестве критерия внимание, напряжение или радость, которые текст будет вызывать у своих читателей — эти чувства не могут быть учтены компьютерами, если они не количественные (существует «наука», называемая психометрией, которая занимается количественной оценкой чувств, желаний и т. д.). Здесь мы видим еще одну особенность компьютеров: они обедняют все, что они преобразуют относительно содержания. (Я пытаюсь здесь оставить в стороне преобразования формы, такие как подтверждение текста; кроме того, это просто хранение того, что уже количественно, такое как буквы текста или фотографий, не входит в мое понятие «обеднение».)

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

Я не думаю, что программисты должны бросать свою профессию, разве что в крайних случаях: если для них есть работа, она нужна обществу. Вопрос в том, как сбалансировать такое одностороннее, грязное мышление. На лекциях, которые я читаю профессионалам по этой теме (под названием «Нищета обработки данных»), некоторые люди предлагают спорт как терапию. Я упоминаю об этом потому, что при силовом спорте нужно действовать с автоматическими рефлексами, на подсознательном уровне – мысли слишком медленные если применять их в движении, нужно использовать мышцы, а мысли парализуют (читатель может убедиться в этом, пытаясь сделать сознательный каждое движение, которое он должен сделать, чтобы захватить карандаш). Вопрос здесь не в том, чтобы исключить мышление, а в том, чтобы сбалансировать грязное программирующее мышление с «живым мышлением».

Короче говоря, я считаю художественную деятельность идеальным противоядием от грязного машинного мышления программистов. Когда активно практикуешь какое-то искусство, не думаешь абстрактно, формально (я, конечно, не имею в виду «компьютерное искусство»). Никто даже не думает в концептуальном плане. Тем не менее, существует вид умственной деятельности, тесно связанный с эстетическими чувствами. Чтобы создать настоящее произведение искусства, нельзя заранее планировать, что делать — импровизацию, наблюдение за результатами и возникающими при этом чувствами. Если какое-то произведение искусства полностью спланировано и предусмотрено заранее, она становится наукой. Для Гете и Наука, и Искусство имели одинаковое происхождение – платонический мир идей, и оба открывали некое знание: первое через концепции, второе через реальные объекты. В лекции, прочитанной в Осло 20 мая 1920 года, Рудольф Штайнер, который редактировал и комментировал научные работы Гете для издания Кюршнера, сказал (см. его» The Arts and their Mission «, Anthroposophic Press, N. York 1964): «Это духовное восприятие и созерцание мира, а не мозговое мышление, которое приводит к искусству…»и» чем больше человек отдается абстрактным мыслям, тем больше он становится чужим искусству. Ибо искусство желает и сосредоточено на жизни».

Читатели могут спросить: но есть ли среди всех видов активного искусства более подходящий для бедных программистов? Я думаю, что любое активное искусство помогло бы необходимой балансировке, описанной выше. Театральная игра развивает острую социальную чувствительность, потому что актеру приходится обращать внимание на сверстников и делать много импровизаций – не каждое движение или интонацию нужно планировать, иначе пьеса теряет свою спонтанность; более того, пьеса должна течь в соответствии с тем, как актеры чувствуют зрителя. Это имеет очень важное уравновешивающее влияние на социальную изоляцию, которую производит программная деятельность. Тем не менее, сценарий должен соблюдаться, поэтому такая деятельность разумно ограничена. Скульптура имеет дело с слишком земным материалом – это пойдет на пользу тому, кто должен развить какую-то внутреннюю форму, но у нашего бедного программиста слишком много формы в мышлении. И так далее, для других искусств. Итак, вот моя рекомендация, основанная на моем собственном опыте: я считаю идеальным противоядием акварельную живопись мокрым по мокрому, то есть на мокрой бумаге. В этой форме живописи используются прозрачные, то есть не жесткие цвета, влажная бумага позволяет легко создавать мелкие, непредвиденные цветовые переходы, а резкие контуры практически невозможно получить. Всегда можно в какой-то степени изменить то, что уже нанесено на бумагу, смешивая на ней цвета, чувствуя, что достиг какого-то удовлетворительного результата. Я использую только основные цвета, желтый, красный и синий, два оттенка каждого. Увлекательно производить с ними всевозможные зеленые оттенки, а также серые и коричневые. Некто может смешать их на белой плитке стены, но использование их, один цвет по другому, сразу на бумаге дает непредвиденные цвета, помогая получить терапевтический эффект. Очевидно, что импровизации цветов и форм следует отдавать предпочтение перед попытками воспроизвести работы известных художников – но это действенный метод развития некоторой техники, преимущественно фигуративной живописи.

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

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

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

Быстрое Определение Скорости

Оригинал статьи. Работы, выполненные с Эльке Рунденштайнер (Elke Rundensteiner). Эта работа стала возможной благодаря поддержке Air Force Office of Scientific Research.

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

Во вводных числовых классах часто упоминаемый пример, в котором используется правило Крамера для решения 25 неизвестных чисел. Многие студенты узнали в своих математических классах, как решить 3 или 4 неизвестных, используя правило Крамера, но никто не рассказал им, как использовать другой метод для большего количества неизвестных. Решение для 25 неизвестных не имеет большого значения, есть много простых методов, которые могут сделать это очень быстро, но правило Крамера не является одним из них! Он примерно в 100,000,000,000,000,000,000,000 раз медленнее, чем стандартный метод сделать расчет. Лучшие суперкомпьютеры стали бы пылью, прежде чем они бы закончили вычисление.

Как вы могли догадаться, подобная разница является исключительной. Это связано с выбором особенно слабого вычислительного метода, правила Крамера. Та проблема, с которой столкнулись Эльке и я, похоже совсем не открывала улучшений. Мы хотели вычислить потоки воздуха или воды вокруг препятствий, таких как провода или крылья. Числительный метод был «вихревым методом», в котором тысячи вызванных небольших торнадо, названные вихрями, использовались для того чтобы представить движение воздуха или воды. Сложность заключалась в том, что нам нужно было найти скорость каждого вихря, чтобы следить за их движением, а скорость каждого зависит от всех остальных вихрей.

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

Это работает, но поскольку мы должны вычислить 9999 расстояний для каждого человека, объем вычислительной работы пропорционален 10000 раз на 9999. Она пропорциональна квадрату количества людей. Если бы было 20 000 человек вместо 10 000, нам пришлось бы преодолевать в четыре раза больше расстояний, а не в два раза. Для большого количества людей, работы над одним человеком просто становится слишком много, для того чтобы это разбирать.

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

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

Как вы уже могли догадаться, основная идея оказалась не особенно оригинальный; реальный тест был в эффективном распределении людей (вихрей) в неправильном паттерне. Вот картина, как Элке и я сгруппировали вихри вместе:

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

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

Вихри: 400 800 1600 3200 6400 12800 25600

Старое время: 9.1 36.3 151.9 586.8 2354.1 9404.8 37556.0

Новое время: 4.7 10.6 25.1 55.4 128.5 286.3 597.8

Соотношение: 2 3 6 11 18 33 63

Таким образом, новый метод уже в 63 раза быстрее для 25 000 вихрей, и это даст еще больше для большего количества вихрей.

Чтобы представить это в перспективе, это разница между получением результатов вычислений на следующий день или через два месяца. Возможно, вы сможете жить с первым, но, вероятно, не со вторым. Я все еще использую эту схему для своих вычислений, хотя другие исследователи, такие как Карриер, Грингард и Рохлин (Carrier, Greengard и Rokhlin), сформулировали аналогичные схемы, которые все еще быстрее. Они также более сложные: люди носят наушники и получают шум младенцев по радио. Когда-нибудь я напишу или получу одну из этих процедур.

Некоторые ссылки:

Van Dommelen, L. L. (1985) Adaptive-panel vortex summation for the CYBER 205. 38th Annual Meeting Div. Fluid Dynamics, Bulletin of the American Physical Society30.

Van Dommelen, L. L. & Rundensteiner, E. A. (1989) Fast solution of the two-dimensional Poisson equation with point-wise forcing. Journal of Computational Physics 83, 126-147.

Carrier, J., Greengard, L. \& Rokhlin, V. (1986) A fast adaptive multipole algorithm for particle simulations. Yale University Research Report YALEU/DCS/RR-496.

Greengard, L. \& Rokhlin, V. (1988) On the efficient implementation of the fast multipole algorithm. Yale University Research Report YALEU/DCS/RR-602.

Страница 1 из 2