Разработка параллельного алгоритма вычисления кэш-рейтинга в системах кэширования

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

1

http://naukovedenie.ru 137TVN214

УДК
519.688

Кудухов Алан Нодарович

ФГБОУ ВПО «Северо-Кавказский горно-металлургический институт

(государственный технологический университет)»

Россия, Владикавказ1

Аспирант кафедры информационных систем в экономике

E-Mail: Kuduh-mail@yandex.ru

Разработка параллельного алгоритма вычисления

кэш-рейтинга в системах кэширования

Аннотация: Автоматизация технологических процессов промышленных предприятий 

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

В целях увеличения производительности в высоконагруженных приложениях и 

системах, 
используют 
технологию 
кэширования, 
которая 
применяется 
в 
качестве 

универсального 
средства, 
позволяющего 
ускорить 
обработку 
и 
анализ 
постоянно 

возрастающего 
потока 
информационных 
данных 
промышленных 
предприятий 
и 

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

Важным фактором, влияющим на эффективность любой системы кэширования, 

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

информационных объектов в системах управления промышленными предприятиями.

Таким образом, очевидна актуальность предположенного в данной статье способа 

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

Ключевые слова: Кэширование, кэш-память, алгоритм замещения, кэш-рейтинг 

объекта, двоичное дерево поиска, параллельный алгоритм.

Идентификационный номер статьи в журнале 137TVN214

1 362911, Северная Осетия-Алания, п. Завадской, ул. Дальняя 31

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

2

http://naukovedenie.ru 137TVN214

Современные задачи крупных промышленных предприятий, связанные с хранением и 

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

надежности и масштабируемости[1].

Создание и эффективное функционирование на предприятии информационных систем 

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

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

Использование кэширования в информационных системах может дать следующие 

преимущества:

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

•
уменьшение среднего значения времени ожидания пользователем запрошенных 
данных;

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

Важным фактором, влияющим на эффективность любой системы кэширования, 

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

Рассмотрим стандартный алгоритм кэширования данных (рис.1).

От того на сколько алгоритм замещения прогнозирует будущее состояние запросов, 

зависит 
эффективность 
всей 
системы 
кэширования. 
Интеллектуальностьалгоритма 

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

Математически коэффициент отражающийинтеллект алгоритма кэширования можно 

представить следующим образом:

(Q =

S

L) → 1, 
(1)

где𝑄 –
коэффициент, 
отражающийколичество 
запросов 
обрабатываемых 
кэш
системой;

𝑆 – количество запросов за определенное время;

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

3

http://naukovedenie.ru 137TVN214

𝐿 – количество кэш-попаданий.

Необходимо отметить, что не только алгоритм замещения играет важнуюроль в 

системах кэширования, но и способ хранения данных, а также возможность параллельной 
обработки данных в кэш-памяти [2].

Рис. 1. Стандартный алгоритм кэширования данных

Так как основной задачей кэширования является сохранение и поиск объектов, то 

следует заметить, что время выполнения основных алгоритмов не должно зависеть от 
количества объектов в кэш-памяти. Для решения данной проблемы, предлагается 
использовать структуру данных «двоичное дерево поиска», которая выполняет основные 
функции (добавления, удаления, поиск) за время 𝑂 (𝑙𝑜𝑔2 𝑁),где 𝑁– количество объектов в 
кэш-памяти.

Двоичное дерево поиска (Binary Search Tree, BST) – это двоичное дерево, с каждым 

из внутренних узлов которого связан ключ, где ключ в любом узле больше или равен ключам 
во всех узлах левого поддерева этого узла и меньше или равен ключам во всех узлах правого 
поддерева этого узла [3, 4].

Начало

Запрос объекта из кэш
памяти

Объект в кэш
памяти?
Да

Получить объект из  

основной памяти

Нет

В кэш-памяти есть 
свободное место?

Освободить память для 

объекта

Нет

Добавить объект в кэш
память

Обновить рейтинг объекта 

в кэш-памяти

Получить объект из кэш
памяти

Конец

Да

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

4

http://naukovedenie.ru 137TVN214

Основные свойства двоичного дерево поиска:

1.
Каждый узел имеет не более двух дочерних узлов;

2.
Каждый 
узел 
содержит 
ключ 
и 
значение 
и 
для 
него 
выполняются 

следующиеусловия:

ключи всех узлов левого поддерева меньше значения ключа родительского узла;

ключи всех узлов правого поддерева больше значения ключа родительского узла;

Математические свойства двоичных деревьев:

1.
Двоичное дерево с 𝑁 внутренними узлами имеет 𝑁 + 1внешних узлов;

2.
Двоичное дерево с 𝑁 внутренними узлами имеет 2𝑁 ссылок: 𝑁 − 1 ссылок на 

внутренние узлы и 𝑁 + 1 ссылок на внешние узлы;

3.
Высота двоичного дерева с 𝑁 внутренними узлами не меньше 𝑙𝑜𝑔2 𝑁 и не больше 

𝑁 − 1.

На рис. 2 представлена структура двоичного дерева поиска, для хранения объектов в 

памяти.

Рис.2. Двоичное дерево поиска

Такоепредставление данных в памяти позволяет оптимизировать процесс поиска 

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

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

Алгоритм поиска объекта в кэш-памяти приведен на рис. 3.

Время выполнения функции поиска объектов в кэш-памяти в худущем случае занимает 

время 𝑂(𝑙𝑜𝑔2 𝑁). Но время вычисления кэш-рейтингов всех объектов занимает в худшем и 

First
Узел

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

5

http://naukovedenie.ru 137TVN214

даже в лучшем случае𝑂(𝑁). В целях уменьшения времени вычисления кэш-рейтинга объектов 
предлагается использовать методы параллельного программирования [5-8].

Параллельное программирование – это техника программирования, которая использует 

преимущества 
многоядерных 
или 
многопроцессорных 
компьютеров 
и 
является 

подмножеством более широкого понятия многопоточности (multithreading).

Идея распараллеливания вычислений основана на том, что большинство задач можно 

разбить на набор меньших задач, которые могут быть решены одновременно [9].

Параллельные вычисления существуют в следующих формах:


параллелизм на уровне битов;


параллелизм на уровне инструкций;


параллелизм данных;


параллелизм задач.

Рис.3. Алгоритм поиск объекта в кэш-памяти

Начало

Получить головное элемент 

дерева и присвоить переменной 

Temp=First

While(Temp!=Null)

If(Temp.Value<=Value)

Temp=Temp.Left
Temp=Temp.Rigth

Да
Нет

If(Temp.Value==Value)

Нет

Конец

Получить хранимый 

объекта

Temp.GetObject()

Да

Получить объект из очереди 

запросов

Object=Queue.GetItem()

Создать поток вычислений

Обновить 

параметры(T, Fr, Tload)

объекта

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

6

http://naukovedenie.ru 137TVN214

Максимальное ускорение, которое можно получить от распараллеливания программы 

на𝑀процессоров, дается законом Амдала [10]:

𝑆 =

1

(𝑃)+1−𝑃

𝑀

,
(2)

где 𝑀– количество ядер на процессоре; 𝑃 – объем вычислений, который может быть 

получен последовательными вычислениями; 1 − 𝑃– объем вычислений, который может быть 
распараллелено идеально.

Таким образом, если размер кэш-памяти – 𝐿, а время вычисления одного кэш-рейтинга 

–𝐶, то время вычисления всех объектов в кэш-памяти можно определить следующим образом:

𝑇 = 𝐿 ∗ 𝐶.
(3)

Следовательно, 
если 
воспользоваться 
возможностями 
параллельного 

программирования, то время вычисления всех рейтингов можно уменьшить в 𝑁раз:

𝑇 =

𝐿∗𝐶

𝑀 .
(4)

Алгоритм параллельного вычисления кэш-рейтинга объектов в виде псевдокода 

приведен на рис.4.

Рис. 4. Псевдокод алгоритма параллельного вычисления кэш-рейтинга объектов

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

вычисления кэш-рейтинга в виде алгоритма (рис. 5).

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

7

http://naukovedenie.ru 137TVN214

Рис. 5. Параллельный алгоритм вычисления кэш-рейтинга объектов

Начало

Определить количество потоков

CountThread=Processor.Count

Вызвать функцию создания 

потоков в параллельном режиме

Создать 

независимый поток 

вычисления

Создать 

независимый поток 

вычисления

While(Left!=NULL)

Установить блокировку

Monitor.Enter(object)

While(Rigth!=NULL)

Получить параметры 

объекта

T, Fr, Tload

Нейронная сеть

Вычислить кэш
рейтинг

Найти минимальный кэш-рейтинг

Удалить найденный объект

Конец

Получить головной элемент 

дерева и присвоить 

переменной Temp=Tree.Frist

Left=Temp.Left & 
Rigth=Temp.Rigth

Получить параметры 

объекта

T, Fr, Tload

Снять блокировку
Monitor.Exit(object)

Добавить в массив 
вычисленный кэш
рейтинг

Получить параметры 

объекта

T, Fr, Tload

Нейронная сеть

Вычислить кэш
рейтинг

Получить параметры 

объекта

T, Fr, Tload

Добавить в массив 
вычисленный кэш
рейтинг

Left=Left.Next
Rigth=Rigth.Next

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

8

http://naukovedenie.ru 137TVN214

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

Заключение

Таким образом, увеличение производительности кэширования зависит не только от 

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

В данной статье был предложен способ хранения данных в кэш- памяти, в виде 

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

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

9

http://naukovedenie.ru 137TVN214

ЛИТЕРАТУРА

1.
Кудухов А.Н. Особенности кэширования данных в информационных системах // 
Наука, Техника, Инновации 2014: сборник статей Международной научнотехнической конференции (25-27 марта 2014 г., г. Брянск). – Брянск: НДМ, 2014. 
С. 226-232.

2.
Кудухов А.Н. Анализ методов и технологий параллельных вычислений для 
обработки информации// Электронный научный журнал APRIORI. Серия: 
Естественные и технические науки. [Электронный ресурс]. – Краснодар: 2014, 
№1.–
Режим доступа: http://www.apriori-journal.ru/seria2/1-2014/Kuduhov.pdf 

(доступ свободный) – Загл. с экрана.

3.
СеджвикР.Алгоритм на C++. – М.:Изд-во «Вильямс», 2011. – 1051 с.

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

5.
Шамим Эхтер, Джейсон Робертс. Многоядерное программирование. – М.:Издво «Питер», 2010. – 316 с.

6.
Воеводин В.В., Воеводин В.В. Параллельные вычисления. – СПб.: БХВПетербург, 2002 – 608 с.

7.
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию 
автоматов, языков и вычислений. – М.: Вильямс, 2002 – 528 с.

8.
Стивен С. Алгоритмы. Руководство по разработке. – СПб.: БХВ-Петербург, 2011 
– 720 с.

9.
Джеффри Р. Windows для профессионалов: создание эффективных Win32 
приложений с учетом специфики 64-разрядной версии Windows / Пер, англ. - 4-е 
изд. - СПб; Питер; М.: Издательско-торговый дом "Русская Редакция", 2001. 752с.

10.
Борееков А. В., Харламов А. А.Основы работы с технологией CUDA.М.: ДМК 
Пресс, 2010.232 с.

Рецензент: Кумаритов Алан Мелитонович, профессор, д.т.н., заведующий кафедрой 

Информационных систем в экономике, ФГБОУ ВПО «Северо Кавказский горно
металлургический институт (государственный технологический университет)».

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 2, март – апрель 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

10

http://naukovedenie.ru 137TVN214

Alan Kuduhov

«North Caucasian Institute of Mining and Metallurgy (State Technological University)

Russia, Vladikavkaz

E-Mail: Kuduh-mail@yandex.ru

The development of parallel algorithm of cache-rating’s 

calculation in caching systems

Abstract: The article suggests method of storing data in a cache-memory, which allows 

decreasing the time of search operation and removal of the object from the cache, and also developed 
the algorithm of parallel computing cache-rating of objects, which increases the productivity of 
cache system.

Automation of technological processes of the industrial enterprises directly connected with 

the development and implementation of information systems. Today the volume of information 
increases rapidly, which increases the processing time information when executing multiple queries 
to the database.

In order to increase performance in high-load applications and systems is used caching 

technology, which is used as a universal means to expedite the processing and analysis of the
constantly-increasing flow of information data of industrial enterprises and providing data to end 
users. The main idea of the caching is to store information in the intermediate memory with fast 
access, which may be relevant in the future.

An important factor influencing the effectiveness of any system caching, is the choice of 

substitution strategy objects in the cache, because it defines a set of objects available to the user of 
the information system with less delay than delay access objects derived from main memory. 
Consequently, the realization of more efficient replacement strategies which allow to increase the 
effectiveness, as the cache system and the information system should be considered a key moment in 
the development of intelligent systems cached of information objects in the control systems of 
industrial enterprises.

Thus, the obvious relevance expected in this article the method of storing data in cache 

memory that can reduce the execution time of operations of search and removal of the object from 
the cache. Also the algorithm of parallel computing cache rating objects, providing increased 
performance of cache system.

Keywords: Caching, cache, replacement algorithm, the cache object rating, binary search 

tree, a parallel algorithm.

Identification number of article 137TVN214