На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: Qraizer
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Вопрос про PAE для решения прикладной задачи , ОС Linux
    Народ, требуется консультация.
    На ПК решается прикладная комбинаторная Задача Коммивояжера (ЗК) методом динамического программирования достаточно большой размерности (минимум надо решить ЗК для числа городов Ng=26).

    На ПК установлено более 4Гб RAM и Intel-процессор с поддержкой PAE.
    Вопрос такой: можно ли в Linux kernel 3.13 в прикладной 32-разрядной программе задействовать более 4Гб RAM?
    Может есть какие-либо возможности в современных 32-bit компиляторах C/C++ использовать не 32-разрядные указатели, а 36-разрядные указатели (PAE)?

    При решении ЗК (Ng около 26-30) размер каждой структуры данных не превышает 4Гб, но общее адресное пространство данных может превысить 4Гб.

    Или в Википедии правильно написано, что PAE - только для ОС и прикладные программы эту технологию использовать не могут?
    Тогда более заморачиваться PAE не буду.

    P.S. 1. При решении ЗК с числом городов Ng памяти минимально требуется примерно (3*Ng+8)*2^(Ng-1) байт. Для Ng=26 эта величина примерно равна 2.9Гб.
    Реально памяти требуется немного больше и на 32-разрядной системе счет аварийно завершается при попытке выделить RAM более 3.1Гб.
    Linux загружаю с LiveCD...
    Думаю, что ЗК получится решить и для Ng=26, если ОС Linux поставить на HDD.
    2. Уверенно удается решать ЗК для Ng=25. Теоретически по приведенной выше формуле необходимо 1393Мб RAM, но реально на практике в программе системой выделяется 1565Мб RAM.
    3. 64-bit системы задействовать крайне нежелательно из-за ряда ограничений, при которых будет решаться ЗК. А использование 64-разрядной ОС скорее всего решило бы все вопросы, несмотря на "распухание" 64-разрядного кода по сравнению с кодом 32-разрядным.
      mkudritsky
      Какой-то очень уж неэффективный алгоритм. Методом ветвей и границ можно спокойно решать задачу коммивояжера вплоть до 40-60 городов без использования кучи памяти: статья на хабре
        PAE предполагает кардинально иную по сравнению с плоской модель памяти, посему она обязана быть поддержана на привилегированном уровне, куда с прикладного уровня ОС никого не пустит (если это нормальная ОС, конечно). Учитывая сильное воздействие на архитектуру адресного пространства в целом, локально поддержать PAE каким-нибудь драйверочком тоже не выйдет, разве что он должен будет трапать все страничные отказы и эмулировать обычное адресное пространство для всех остальных служб ядра ОС, что, впрочем, можно сделать виртуализацией.
        Отсюда вывод "PAE - только для ОС и прикладные программы эту технологию использовать не могут" выглядит как достоверный, но не абсолютный. Если же ОС поддерживает PAE, то у неё уже должны быть соответствующие API для его поддержки. К примеру WinAPI таковое имеет, однако оно неудобно для такой постановки задачи. Другое дело, что используя PAE со стороны драйверочка, можно локально для своего приложения предоставить более-менее удобное нечто.

        P.S. Конкретно по Windам. Использование 64-битной ОС даже для 32-битных приложений всё равно даст больше памяти по сравнению с 32-битной ОС. Так что если проблема конкретно в архитектуре ПО, то его вполне можно оставить 32-битным, но запускать в 64-битном окружении. Кроме того, даже в 32-битной ОСи можно попробовать получить 3Гб, но начиная с XP SP2 это довольно затруднительно.
          Qraizer, спасибо за информацию!
          Я так и думал. Как-то сомнительно, что в прикладной программе команда sizeof выдаст размер указателя в 36 бит. :)
          Эх, жалко. Но ладно, буду надеяться, что все-таки для Ng=26 хватит 4Гб RAM.

          Кстати, ЗК будет решаться на ПК под управлением Linux, а не Win.
          Это одно из требований стороны, которой такая программа нужна.
          (Как, кстати, и требования 32-битности).

          Pacific, к сожалению, метод ветвей и границ (МВГ) имеет ряд недостатков по сравнению с методом динамического программирования (МДП).
          1. МДП дает 100% вероятность решения ЗК вне зависимости от матрицы расстояний. (Ну, разумеется, для числа городов, которое МДП может осилить).
          Если же использовать МВГ, то всегда будут существовать матрицы, при которых процесс поиска решения завершится аварийно.
          На то ЗК и является труднорешаемой комбинаторной задачей.
          То есть МВГ ищет решение не со 100% вероятностью. Но, конечно, чем меньше размерность задачи (число городов), тем ближе эта вероятность к 100%.

          2. МДП позволяет решать такие разновидности ЗК, как динамическая ЗК (это когда матрица расстояний зависит от того, сколько городов прошел коммивояжер).
          Или вообще если надо будет учитывать, сколько топлива израсходовал коммивояжер на своей грузовой машине, развозя товары по городам. Чем больше товаров развезет коммивояжер, тем легче становится машина и тем меньше тратится топлива.
          Для подобного рода обобщения Задачи Коммивояжера МДП приспособлен очень хорошо.
          А вот для МВГ очень непросто подобрать эффективную нижнюю оценку оставшегося пути движения коммивояжера.
          Сообщение отредактировано: mkudritsky -
            Цитата mkudritsky @
            То есть МВГ ищет решение не со 100% вероятностью.

            С чего бы это? Он всегда находит оптимальное решение, вопрос только как быстро. Завершиться аварийно тоже не может, если правильно написан. Для большинства практических применений 40-60 городов он обрабатывает за приемлемое время.
            Сообщение отредактировано: Pacific -
              Pacific, чтобы прекратить споры по этому вопросу, скажу так - мною тоже будет создаваться программа решения классической ЗК методом ветвей и границ.
              Вернее, не МВГ, а некий композитный алгоритм: поиск методом ветвей и границ по графу состояний, формируемым методом динамического программирования.

              Примерно в 2003 году мною такие программы уже создавались, но на языке Pascal.
              Теперь хочу все тоже самое сделать на C++/C.
              Кстати, мне ЗК удавалось решить и для 200 городов с вероятностью около 80%

              P.S. Под аварийным завершением работы я подразумевал факт, что решение не будет найдено вообще. Но согласен - для 40..60 городов вероятность успешного поиска решения классической ЗК близка к 100%. Но не равна 100%! И это я в 2003 году в качестве нижней оценки использовал решение Задачи о Назначениях, которая считается не самой лучшей нижней оценкой...
              Сообщение отредактировано: mkudritsky -
                mkudritsky, судя по докам, да хоть в той же вики:

                Цитата
                Physical Address Extension (PAE) — режим работы встроенного блока управления памятью x86-совместимых процессоров, в котором используются 64-битные элементы таблиц страниц (из которых для адресации используются только 36 бит), c помощью которых процессор может адресовать 64 ГБ физической памяти (вместо 4 ГБ, адресуемых при использовании 32-разрядных таблиц), хотя каждая задача (программа) всё равно может адресовать максимум до 4 ГБ виртуальной памяти

                Следовательно, если нужно более 4Gb памяти - нужно пересмотреть архитектуру вычислений, а именно - форкнуть несколько процессов, организовать между ними обмен по SHM или IPC. Тогда суммарный объем памяти можно сделать более 4Gb. И не путать с многопоточностью.
                  Цитата JoeUser @
                  хотя каждая задача (программа) всё равно может адресовать максимум до 4 ГБ виртуальной памяти

                  На виртуальную память можно отобразить любой участок физической памяти, другое дело, что переключение "окон" должно осуществляться средствами ОС.
                  Сообщение отредактировано: shm -
                    Цитата JoeUser @
                    Следовательно, если нужно более 4Gb памяти - нужно пересмотреть архитектуру вычислений, а именно - форкнуть несколько процессов, организовать между ними обмен по SHM или IPC. Тогда суммарный объем памяти можно сделать более 4Gb. И не путать с многопоточностью.
                    Необязательно. DOS-приложения оперировали 20-битным адресным пространством, каждый указатель был 16-битным, и тем не менее весь 1Мбайт был вполне доступен приложению. Модель памяти была соответствующая, там были и т.н. far-указатели.
                    Когда я говорил о кардинальной смене архитектуры, я имел в виду именно это. Плоская модель тут не подходит, а остальные не поддерживаются ОСью, что ставит крест на сосуществовании приложения с явным PAE с остальными приложениями. И даже ядерными процессами, т.к. те тоже не разу не знают про неплоскую модель.
                      Цитата Qraizer @
                      Необязательно.

                      А как можно еще?
                        Ну вот как это делал Watcom compiler. У него была 32-битная far-модель, специально для случаев, когда 4Гбайтового адресного пространства не хватало. Пара 16-битный селектор сегмента + простой 32-битный указатель. Разумеется, поддержка со стороны как исполнительного окружения, так и компилятора должна была быть. С компилятором понятно, а исполнительным окружением выступали DOS экстендеры типа DOS4GW или 286/386 от Phar Lap, предоставлявшим приложениям полноценный DPMI и поддерживающие виртуальную память.
                        Сообщение отредактировано: Qraizer -
                          Ну теория древняя и известная. Вопрос ТС задал конкретно для 32-битного линуха. Для него как иначе?
                            Цитата mkudritsky @
                            Как-то сомнительно, что в прикладной программе команда sizeof выдаст размер указателя в 36 бит.
                            Эх, жалко. Но ладно, буду надеяться, что все-таки для Ng=26 хватит 4Гб RAM.

                            Ты понимаешь разницу между физическими адресами RAM и виртуальными адресами, используемыми в прикладных программах?
                            Использование PAE расширяет физический адрес до 36 бит и позволяет использовать RAM более 4Гб. Но эти адреса доступны только ядру ОС, а прикладные 32-битные программы используют виртуальные 32-битные адреса, которые в принципе не могут (одновременно) адресовать более 4Гб. К тому же нужно учитывать, что 4Гб это максимальный размер виртуального адресного пространства (ВАП) 32-битного приложения, а реально для своих нужд программа может использовать менее 3Гб (одновременно) адресуемых (приватных) данных, т.к. не менее 1Гб адресов ВАП зарезервировано за ОС и еще какая-то часть занята образами самой программы, используемых ею dll и разнообразными служебными регионами памяти (стеками потоков, кучами, переменными окружения и т.п.). В итоге, 32-битная программа может (одновременно) использовать только менее 3Гб памяти независимо от размера RAM (даже если RAM всего 2Гб или менее, часть данных будет хранится и подкачиваться из файла подкачки, что скажется только на быстродействии программы, но не на ее принципиальной работоспособности).

                            Теперь, что означает "одновременно" адресовать менее Х Гб. Если мы не можем в свой ВАП одновременно проецировать более X Гб физических адресов, то в принципе (как намекнул shm) можно организовать последовательное блочное проецирование физ.адресов любого размера в некий ограниченный регион виртуальных адресов ("окно") - по принципу блочного файл-маппинга. В винде для этого есть спец.технология под названием AWE (Address Windowing Extensions), которая позволяет приложению непосредственно выделять доп.физ память и проектировать ее в окно виртуальных адресов. В линухе я не силен, но беглый поиск показывает, что вроде как прямого аналога AWE в нем нет, но есть возможность создания собственной файловой системы (tmpfs и т.п.) в RAM с блочным проецированием данных в ВАП через mmap.

                            Кроме того, если размер RAM превышает 3-4Гб, то как отметил JoeUser, можно хранить данные в нескольких процессах. При этом второй процесс можно использовать как "активно" для параллельной обработки данных, так и "пассивно" - только как хранилище дополнительной разделяемой памяти, которая будет использоваться основным процессом в том же режиме блочного проецирования в "окно" своего ВАП.
                            PS: В винде такой подход организовать даже проще (через именованный файл-маппинг в памяти), чем использовать AWE (нужны особые привелегии и освоение нового АПИ). В линухе - не знаю (проще ли такой подход по сравнению с tmpfs или нет).
                            Сообщение отредактировано: leo -
                              Цитата Qraizer @
                              Необязательно. DOS-приложения оперировали 20-битным адресным пространством, каждый указатель был 16-битным, и тем не менее весь 1Мбайт был вполне доступен приложению. Модель памяти была соответствующая, там были и т.н. far-указатели.


                              Прямо в яблочко! Поэтому-то я и задал вопрос.
                              В MS DOS, несмотря на 16-битные указатели, в защищенном режиме работы микропроцессора i80286 можно было адресовать до 2Мб (вроде так) RAM ПК.
                              ИМХО адресация осуществлялась в два такта микропроцессора.
                              И была среда программирования, позволяющая создавать программы для защищенного режима работы i80286.
                              Называлась эта среда программирования Borland Pascal 7.0 for DOS.
                              В защищенном режиме работы i80286 в Borland Pascal размер доступной динамической памяти ("кучи" по-паскалевски) был больше 1Мб.
                              Кстати, скорость работы программ в защищенном режиме работы процессора и в реальном режиме работы была одинакова! Это говорило о том, что адресация верхней памяти происходила с одинаковой скоростью, как и адресация памяти до 1Мб.

                              Но сейчас, в режиме PAE работы некоторых процессоров Intel все не так.
                              Прикладной программе на все про все доступно только 4Гб RAM, а вот для ОС доступно памяти до 64Гб включительно.
                              Например, ОС в этой "верхней" памяти может создавать RAM-диски, кэши... Наверное, виртуальные машины тоже в памяти выше 4Гб может размещать...

                              Я, собственно, хотел сэкономить.
                              При решении ЗК методом динамического программирования создается массив указателей размерности порядка одного миллиарда.
                              В 32-бит системе этот массив занимает меньше 4Гб RAM, т.к. каждый указатель занимает 4 байта.
                              В 64битной системе эта структура займет уже 8Гб RAM! Так как размер указателя равен 8 байтам.
                              Я ожидал, что в режиме PAE 32-битного процессора эта структура будет занимать 5Гб RAM (36bit на один указатель - то есть 5 байт при округлении в бОльшую сторону). Все же 5Гб лучше, чем 8Гб.

                              Но, как видим, оказалось, что я мечтаю напрасно.
                              Сообщение отредактировано: mkudritsky -
                                Цитата mkudritsky @
                                Цитата Qraizer @
                                Необязательно. DOS-приложения оперировали 20-битным адресным пространством, каждый указатель был 16-битным, и тем не менее весь 1Мбайт был вполне доступен приложению. Модель памяти была соответствующая, там были и т.н. far-указатели.


                                Прямо в яблочко! Поэтому-то я и задал вопрос.

                                Нет никакого чуда - чтобы это понять, надо почитать про организацию памяти x86.
                                Она была сегментная - по 64К.
                                Данные самой программы содержались в сегментах, для доступа к ним предварительно загружался
                                сегментный регистр и тогда в пределах сегмента достаточно программных указателей 16 бит.

                                В пределах одного сегмента хватало 16 бит, но адрес фактически всё равно состоял
                                из 2- 16 битных слов. Сегмента и смещения. Причём значение сегмента сдвигалось влево на 4 бита
                                и складывалось со смещением (аппаратно). Так получался 20-битный абсолютный указатель, а вся память - 1М.

                                У х86 есть команды для работы в пределах 1-го 64К сегмента, а есть - в пределах 1М.
                                Просто для таких возможностей в теле команды присутствует значения не только смещения, но сегмента
                                (дополнительное слово 16 бит).
                                У 286 процессора в реальном режиме - также, а в защищённом - до 16М. Адресная шина 24 бита.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0408 ]   [ 17 queries used ]   [ Generated: 29.03.24, 00:05 GMT ]