НАУКА и ОБРАЗОВАНИЕ

Файл статьи: 01-.pdf (23339.25Кб)

Актуальной задачей современной теории сигналов является поиск бинарных фазоманипулированных сигналов (кодов), у которых боковые лепестки автокорреляционной (АКФ) и взаимно корреляционной (ВКФ) функций имеют уровни меньшие либо равные заданным значениям (M_A и M_V соответственно). Такие сигналы можно представить в виде (1) [1, 2]:

где n > 2 – битовая длина такого сигнала, S(t) - огибающая сигнала, w₀ – частота несущей, q = {0, p} – фаза.

Биты сигнала можно представить в виде бинарного множества коэффициентов , в котором

.

Множество уровней боковых лепестков АКФ задается формулой (2):

, где x y = x XOR y = (x + y) mod 2 - операция исключающего ИЛИ над битами x и y.

Отсюда для кода, удовлетворяющего условию поиска по АКФ, необходимо выполнение неравенства (3):

для .

Вероятность удовлетворения произвольным кодом из диапазона условию поиска по АКФ можно оценить, используя формулу (4):

Вид зависимости (4) представлен на рис. 1.

Из соотношений (2) и (3) вытекают следующие тождества, позволяющие сократить время поиска по уровню бокового лепестка АКФ [3]:

где – зеркальное отображение бит последовательности S.

Как будет показано ниже, вероятность (4) является также вероятностью возникновения состязательности между единицами выполнения в параллельной среде.

Множество уровней лепестков ВКФ последовательностей и задается формулой (6):

Для выполнения условия поиска по ВКФ должно выполняться неравенство (7):

для

Из соотношений (5) следует, что вероятность значений всех бит кода, найденного по условию АКФ, равна 0.5. Таким образом, из формул (4) и (7) можно получить полную оценочную вероятность удовлетворения условий поиска кодов по АКФ и ВКФ – среднюю вероятность для кодов из диапазона перебора.

где

Вид функции (8) для 33-х битового кода представлен на рис. 2.

Архитектура параллельного пермутатора

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

Основными механизмами повышения скорости поиска в представленной программе (рис. 3) являются использование соотношений (5) для понижения количества итераций при переборе в ~2 раза, а также использование механизма параллельного перебора, дающего выигрыш в производительности прямо пропорциональный количеству процессоров в распространенных сегодня SMP-системах.

При запуске задачи ядро приложения (основной поток) инициализирует дескриптор вычислителя, структура которого зависит от количества процессоров, обнаруженных в системе. При обнаружении нескольких процессоров в основном потоке из отдельно создаваемой кучи выделяется собственная память потоков, инициализируемая элементами вектора, являющимися целочисленными переменными произвольной точности n, кратной 32 битам:

.

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

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

При поиске произвольный код из диапазона [0, 2ⁿ) с вероятностью p_A удовлетворяет критерию поиска по максимально допустимой АКФ. В этом случае поток, владеющий кодом, начинает последовательный перебор кодов из списка найденных кодов.

Проверка соответствия кода условиям по АКФ (3) и ВКФ (7) производится посредством двух функций, реализующих проверку уровней боковых лепестков функции (со сдвигом – ConvolutionSh) и основного лепестка функции (без сдвига – ConvolutionNsh).

Функция ConvolutionNsh проверки основного лепестка корреляционной функции заключается в простом поразрадном сложении битов сигналов по модулю 2 (операция исключающего ИЛИ) и подсчете бит результата.

Тогда проверка по формуле (3) соответствует одному вызову ConvolutionSh для lpSignal1 = lpSignal2. Проверка (7) является последовательным вызовом ConvolutionSh(lpSignal1, lpSignal2, …), ConvolutionSh(lpSignal2, lpSignal1) и ConvolutionNsh(lpSignal1, lpSignal2).

Список найденных кодов является разделяемой памятью, размером 1Мб, а также файлом, создаваемый при переполнении области списка, находящейся в ОЗУ. Разделяемый доступ требует использования механизмов синхронизации, которые, в свою очередь, создают условия возникновения состязательности между потоками. При этом, как видно из рис. 2, вероятность того, что произвольный код будет удовлетворять условиям АКФ и ВКФ с набором сигналов из общей памяти, при разумном выборе параметров поиска, будет минимальной. Поэтому для синхронизации рабочих потоков используется механизм, основанный на использовании критических участков кода со значением спин-счетчика, равным 4000 [4], а также на модели переменных условий (на вручную сбрасываемом событии). Функции, представленные здесь на языке C с использованием функционала Win32 SDK, реализуют вхождение в критические участки кода, различаемые по требуемому доступу к разделяемым ресурсам:

/*PCOMPDESCRIPTOR – тип указателя на структуру, которая описывает текущее состояние вычислителя.*/
/*Среди своих полей содержит:*/
/*CRITICAL_SECTION cs – критический участок кода со спин счетчиком, равным 4000.*/
/*HANDLE hEvent – автоматически сбрасываемое неименованное событие, создаваемое в несигнальном состоянии.*/
/*volatile DWORD dwThreadCounter – счетчик потоков, вошедших в критический участок кода для чтения (функцией LockRead).*/
/*volatile BOOL bSerialization – флаг сериализации – по умолчанию включен для SMP-систем, отключен для однопроцессорных систем.*/
/*LockWrite – вхождение в критический участок кода для записи.*/
BOOL LockWrite(PCOMPDESCRIPTOR lpComp)
{
  if (lpComp->bSerialization)
  {
    EnterCriticalSection(&lpComp->cs);
    if (lpComp->dwThreadCounter && WaitForSingleObject(lpComp->hEvent, INFINITE) == -1)
    {
      LeaveCriticalSection(&lpComp->cs);
      return FALSE;
    }else if (!lpComp->bSerialization)
    /*Выход из критического участка кода, если во время ожидания была отключена сериализация*/
    LeaveCriticalSection(&lpComp->cs);
  }
  return TRUE;
}
/* LockRead – вхождение в критический участок кода для чтения разделяемых ресурсов.*/
BOOL LockRead(PCOMPDESCRIPTOR lpComp)
{
  if (lpComp->bSerialization)
  {
    EnterCriticalSection(&lpComp->cs);
    lpComp->dwThreadCounter++;
    LeaveCriticalSection(&lpComp->cs);
  }
  return TRUE;
}
/* UnlockWrite – выход из критического участка кода на запись.*/
VOID UnlockWrite(PCOMPDESCRIPTOR lpComp)
{
  if (lpComp->bSerialization)
    LeaveCriticalSection(&lpComp->lpCS);
}
/* UnlockRead – выход из критического участка кода на чтение.*/
BOOL UnlockRead(PCOMPDESCRIPTOR lpComp)
{
  return !lpComp->bSerialization || (BOOL) InterlockedDecrement((volatile LONG*) &lpComp- >dwThreadCounter) || SetEvent(lpComp->hEvent);
}

В зависимости от режима работы пермутатора – однопоточном или многопоточном – необходимость в приведенном функционале может исчезать, Для включения либо отключения сериализации доступа к разделяемым ресурсам введена функция SetSerialization, вызов которой безопасен в том случае, если имеются потоки, владеющие критическим участком кода на чтение/запись:

BOOL SetSerialization(PCOMPDESCRIPTOR lpComp, BOOL bSerialize)
{
  if (!bSerialize)
  {
    if (!lpComp->bSerialize)
      return TRUE;
    EnterCriticalSection(&lpComp->cs);
    if (lpComp->dwThreadCounter && WaitForSingleObject(hEvent, INFINITE) == WAIT_FAILED)
    {
      LeaveCriticalSection(&lpComp->cs);
      return FALSE;
    }
    lpComp->bSerialization = TRUE;
    LeaveCriticalSection(&lpComp->cs);
    return TRUE;
  }else if (lpComp->bSerialization)
    return TRUE;
  else
  {
    if (!ResetEvent(lpComp->hEvent))
      return FALSE;
    lpComp->dwThreadCounter = 0;
    return TRUE;
  }
}

Исходя и схемы работы вычислителя, а также из (4) и (8) можно оценить сложность представленного алгоритма [5] с учетом параллельной обработки данных (10).

На рис. 6 приведен графический вид зависимости (10) для 33 битовых кодов. На рис. 7 слева приведена та же расчетная зависимость для M_A и M_V таких, что 2 ≤ M_A ≤ 10, 2 ≤ M_V ≤ 15. На рис. 7 справа показано время, выраженное в миллисекундах, потраченное представленным пермутатором для поиска всех 33 битовых кодов с АКФ и ВКФ с уровнями боковых лепестков меньших либо равных M_A и M_V таких, что на двухпроцессорной машине. Рис. 6 показывает соответствие полученного времени поиска кодов с расчетной сложностью алгоритма. Формула (10) также показывает выигрыш при использовании параллельных единиц выполнения, выраженный гиперболическим законом.

Для 33 битового кода, максимальных уровней боковых лепестков АКФ 10 и ВКФ 6 получена зависимость времени вычисления в миллисекундах от количества используемых процессоров (рис. 8).

Заключение

Представленные эмпирические данные показывают хорошее соответствие с ожидаемыми значениями, полученными из представленных выражений, а также эффективность многопоточного синтеза при корректном использовании механизма параллельных вычислений. Хотя представленный продукт жестко привязан к архитектуре Wintel x86 (ядро реализовано на ассемблере для процессоров Intel), он, в принципе, является переносимым на другие платформы имеющие набор инструкций, близкий к семейству Intel P6, а также поддерживающие истинную многозадачность.

Список литературы

1. Шумоподобные сигналы. Анализ, синтез, обработка / В.Е. Грантмахер, Н.Е. Быстров, Д.В. Чеботарев. – СПб.: Наука и Техника, 2005. 400 с.

2. Свердлик М.Б. Оптимальные дискретные сигналы. М.: Советское радио, 1975. 200 с.

3. Чусов А. А. Поиск базиса кодов с наилучшими автокорреляционными свойствами /., Ковылин А. А.,. Родионов А.Ю., Злобин Д. В., Железняков Е. И. //Труды конференции «Вологдинские чтения», Владивосток: Издательство ДВГТУ, 2009 С. 70 - 71.

4. Харт Д. М. Системное программирование в среде Windows: пер. с англ. М.:: Вильямс, 2005. 792 с.

5. Кнут Д. Искусство программирования: в 3 т. Т. 1: Основные алгоритмы: пер. с англ. 3-е изд. перераб. и доп. М.: Вильямс, 2006. 720 с.