Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
О скоростях передачи данных на шинах между кеш-памятью второго и третьего уровней и между процессором и оперативной памятью в современных компьютерах
Get PDFIn this paper, a modern CPU architecture with several different cache levels is described, and current CPU performance limitations such as silicone physical limitations or frequency increase bounds are mentioned. As usual, changes of the currently existing architecture are proposed as a way of increasing CPU performance, data rates on the internal and external CPU interfaces must be known. It would help to assess applicability of proposed solutions and allow to optimize them. This paper is aimed at getting real values of traffic on L2-L3 cache interface inside CPU and CPU-RAM bus load as well as show dependencies of total traffic on the interfaces of interest on the number of active cores, CPU frequency and test type. Measurements methodology using Intel Performance Counter Monitor by Intel is provided and equations that allow to get data rates from internal CPU counters are explained. Both real life and synthetic tests are described. Dependency of total traffic on the number of active cores and dependency of total traffic on CPU frequency are provided as plots. Dependency of total traffic on test type provided as bar plot for multiple CPU frequencies.В данной работе рассматривается архитектура используемых в настоящее время центральных процессоров и ограничения их производительности в современном виде. Так как чаще всего для повышения производительности центральных процессоров предлагаются решения, связанные с изменением существующей архитектуры, необходимо иметь представление о скоростях передачи данных внутри процессора и на шинах, подходящих к нему. Это позволит оценить применимость предлагаемых решений и даст возможность их оптимизировать. В этой статье решается задача измерения реальных скоростей передачи данных на интерфейсе между кеш-памятью второго и третьего уровней внутри процессора и на интерфейсе между процессором и оперативной памятью, а также изучения зависимости численных результатов от количества активных ядер, тактовой частоты процессора и типа проводимого теста. В статье приводится методология проведения измерений с помощью программного инструмента Intel Performance Counter Monitor от компании Intel, а также приводятся формулы для получения итогового результата из полученных в ходе измерений значений. Приведено подробное описание тестов, имитирующих реальную нагрузку на центральный процессор, и синтетических тестов. Зависимости скоростей передачи данных от количества активных ядер и от тактовой частоты процессора представлены в виде графиков. Зависимости скоростей передачи данных от типа теста представлены в виде столбиковых диаграмм для трех различных значений тактовой частоты процессора
Разложение самоподобных функций в системе Фабера–Шаудера
Get PDFLet be a space of right-sided innite sequences drawn from a nite alphabet , . Let \label{rho} \rho(\boldsymbol{x},\boldsymbol{y}) =\sum_{k=1}^{\infty}|x_{k} - y_{k}|2^{-k}- be a metric on , and - the Bernoulli measure on with probabilities p_0,p_1>0, . Denote by an open ball of radius centered at . The main result of this paper iswhere , , tau(x) = 0, if x<0 or x>1,.The family of functions , , is the Faber{Schauder system for the space of continuous functions on .We also obtain the Faber{Schauder expansion for the Lebesgue's singular function, Cezaro curves, and Koch{Peano curves.Пусть - пространство правосторонних бесконечных последовательностей символов алфавита , . Пусть\label{rho} \rho(\boldsymbol{x},\boldsymbol{y}) =\sum_{k=1}^{\infty}|x_{k} - y_{k}|2^{-k}- метрика на , и - мера Бернулли на с вероятностями p_0,p_1>0, . Обозначим через открытый шар радиуса с центром в точке .Основной результат работыгде , , tau(x) = 0, if x<0 or x>1,.Семейство функций , , является системой Фабера-Шаудера в пространстве непрерывных функций на .Также получены разложения в системе Фабера-Шаудера для сингулярной функции Лебега, кривых Чезаро и кривых Коха-Пеано
Об асимптотике решений гармонического осциллятора с интегральным возмущением
Get PDFWe construct the asymptotics for solutions of a harmonic oscillator with integral perturbation when the independent variable tends to infinity. The specific feature of the considered integral perturbation is an oscillatory decreasing character of its kernel. We assume that the integral kernel is degenerate. This makes it possible to reduce the initial integro-differential equation to an ordinary differential system. To get the asymptotic formulas for the fundamental solutions of the obtained ordinary differential system, we use a special method proposed for the asymptotic integration of linear dynamical systems with oscillatory decreasing coefficients. By the use of the special transformations we reduce the ordinary differential system to the so called L-diagonal form. We then apply the classical Levinson’s theorem to construct the asymptotics for the fundamental matrix of the L-diagonal system. The obtained asymptotic formulas allow us to reveal the resonant frequencies, i. e., frequencies of the oscillatory component of the kernel that give rise to unbounded oscillations in the initial integro-differential equation. It appears that these frequencies differ slightly from the resonant frequencies that occur in the adiabatic oscillator with the sinusoidal component of the time-decreasing perturbation.В работе строятся асимптотические формулы для решений гармонического осциллятора с интегральным возмущением при стремлении независимой переменной к бесконечности. Особенностью рассматриваемого интегрального возмущения является колебательно убывающий характер его ядра. Предполагается, что интегральное ядро является вырожденным. Данное обстоятельство позволяет свести исходное интегро-дифференциальное уравнение к системе обыкновенных дифференциальных уравнений. При построении асимптотических формул для базисных решений полученной системы обыкновенных дифференциальных уравнений используется специальный метод асимптотического интегрирования линейных динамических систем с колебательно убывающими коэффициентами. В результате серии специальных преобразований система обыкновенных дифференциальных уравнений приводится к так называемому L-диагональному виду. Асимптотика фундаментальной матрицы L-диагональной системы может быть построена с помощью классической теоремы Н. Левинсона. Полученные асимптотические формулы позволяют выявить так называемые резонансные частоты, т. е. частоты колебательной составляющей ядра, при которых у исходного интегро-дифференциального уравнения имеются неограниченные решения. Как оказывается, эти частоты несколько отличаются от резонансных частот в адиабатическом осцилляторе с синусоидальной колебательной составляющей убывающего во времени возмущения
Новые оценки числовых величин, связанных с симплексом
Get PDFLet and . For a nondegenerate simplex , by we denote the homothetic copy of~ with center of homothety in the center of gravity of and ratio of~homothety . By we mean the minimal such that . By denote the minimal such that is~contained in a translate of~. By we denote the th axial diameter of , i.\,e. the maximum length of~the segment contained in and parallel to the th coordinate axis. Formulae for~, , were proved earlier by the first author. Define We always have We discuss some conjectures formulated in the previous papers. One of~these conjectures is the following. For~every , there exists , not depending on , such that an~inequality holds. Denote by the minimal with such a~property. We prove that ; for , we obtain . If and then . The equality holds if is an Hadamard number, i.\,e. there exists an Hadamard matrix of~order . This proposition is known; we give one more proof with the direct use of Hadamard matrices. We prove that . Therefore, there exists such that is not an Hadamard number and nevertheless . The~minimal with such a property is equal to . This involves and also disproves the following previous conjecture of the first author concerning the characterization of Hadamard numbers in terms of~homothety of simplices: is an Hadamard number if and only if This statement is valid only in one direction. There exists a simplex such that the boundary of the simplex contains all the vertices of the cube . We describe a one-parameter family of simplices contained in with the property These simplices were found with the use of numerical and symbolic computations. %Numerical experiments allow to discover Another new result is an inequality \xi_6\Пусть \(n\in {\mathbb N}, . Для невырожденного симплекса через обозначается результат гомотетии относительно центра тяжести с~коэффициентом гомотетии . Под понимается минимальное \sigma>0, такое что . Через обозначается минимальное \sigma>0, при котором принадлежит трансляту симплекса . Через обозначается -й осевой диаметр , представляющий собой максимальную длину отрезка, принадлежащего и параллельного -й координатной оси. Формулы для , , были ранее доказаны первым автором. Положим Всегда Обсуждаются некоторые гипотезы, сформулированные в предыдущих работах. Одной из них является следующее утверждение. Для любого существует константа \gamma>0, не зависящая от , с которой выполняется неравенство Минимальное c таким свойством обозначается через . Доказывается, что и при n>1 справедливо . Если n>1 и то . Равенство выполняется, если --- число Адамара, т.\,е. существует матрица Адамара порядка . Последнее утверждение известно; приводится ещё одно его доказательство, непосредственно использующее матрицы Адамара. %Полученная ранее общая оценка %для даёт . Доказывается, что . Таким образом, существуют такие , для которых не является числом Адамара и, тем не менее, . Минимальное с таким свойством равно . Это влечёт и %Равенство опровергает гипотезу о характеризации чисел Адамара в терминах гомотетии симплексов, высказанную ранее первым автором: есть число Адамара тогда и только тогда, когда Последнее утверждение оказывается верным лишь в одну сторону. Существует симплекс , для которого граница симплекса содержит все вершины куба . Указывается однопараметрическое семейство симплексов, принадлежащих и обладающих свойством Эти симплексы удаётся найти с помощью комбинации численных и~символьных вычислений. Новым результатом является неравенство \(\xi_6
О контрастных структурах с многозонным внутренним слоем
Get PDFA boundary value problem for a singularly perturbed differential equation of second order is considered in two cases, when one root of the degenerate equation is two-tuple. It is proved that in the first case the problem has a solution with the transition from the two-tuple root of the degenerate equation to one-tuple root in the small neighbourhood of an internal point of the interval, and in the second case the problem has a solution which has the spike in the interior layer. Such solutions are named, correspondingly, a contrast structure of step-type and a contrast structure of spike-type. In each case the asymptotic expansion of the contrast structure is constructed. It distinguishes from the known expansion in the case, when all the roots of the degenerate equation are one-tuple, in particular, the interior layer is multizonal.Рассматривается краевая задача для сингулярно возмущённого дифференциального уравнения второго порядка в двух случаях, в каждом из которых один из корней вырожденного уравнения является двукратным. Доказано, что в первом случае образуется узкий внутренний слой, в котором происходит быстрый переход решения от двукратного корня вырожденного уравнения к простому корню, а во втором случае во внутреннем слое происходит «всплеск» решения. Такие решения называются соответственно контрастной структурой типа ступеньки (КСТС) и контрастной структурой типа всплеска (КСТВ). В каждом случае построено асимптотическое разложение контрастной структуры, существенно отличающееся от известного разложения в случае, когда все корни вырожденного уравнения – простые, в частности, внутренний слой оказывается многозонным
Синтез управления и наблюдателя для слабо нелинейных систем на основе техники псевдолинеаризации
Get PDFIn this paper, an approach to the construction of nonlinear output tracking control on a finite time interval for a class of weakly nonlinear systems with state-dependent coefficients is considered. The proposed method of control synthesis consists of two main stages. At the first stage, a nonlinear state feedback regulator is constructed by using a previously proposed control algorithm based on the State Dependent Riccati Equation (SDRE). At the second stage, the problem of fullorder observer construction is formulated and then it is reduced to the differential game problem. The form of its solution is obtained with the help of the guaranteed (minimax) control principle, which allows to find the best observer coefficients with respect to a given functional considering the worstcase uncertainty realization. The form of the obtained equations made it possible to use the algorithm from the first stage to determine the observer matrix. The proposed approach is characterized by the nonapplicability of the estimation and control separation principle used for linear systems, since the matrix of observer coefficients turned out to be dependent on the feedback coefficients matrix. The use of numerical-analytical procedures for determination of observer and feedback coefficients matrices significantly reduces the computational complexity of the control algorithm. В работе для одного класса слабо нелинейных систем с зависящими от состояния коэффициентами рассматривается подход к построению нелинейного следящего управления по выходу на конечном интервале времени. Предложенный метод синтеза состоит из двух основных этапов. Сначала с помощью ранее предложенного автором алгоритма на основе уравнений Риккати, с зависящими от состояния коэффициентами (State Dependent Riccati Equation – SDRE), находится нелинейный регулятор по состоянию. На втором этапе ставится задача построения наблюдателя полного порядка, которая сводится к задаче дифференциальной игры. Вид её решения получен с помощью принципа гарантированного управления, позволяющего относительно заданного функционала найти наилучшие коэффициенты наблюдателя при наихудшей реализации неопределенностей. Однотипность полученных уравнений позволила для определения матрицы наблюдателя использовать алгоритм решения из первого этапа. Особенностями предложенного подхода являются отсутствие принципа разделения задач синтеза управления и наблюдения, который имеет место в линейных системах, поскольку матрица коэффициентов наблюдателя оказалась зависимой от матрицы коэффициентов обратной связи, и использование численно-аналитических процедур для определения этих матриц, что позволяет значительно снизить вычислительную сложность алгоритма управления.
Анализ типизированных зависимостей включения с неопределенными значениями
Get PDFNull values have become an urgent problem since the creation of the relational data model. The impact of the uncertainty affects all types of dependencies used in the design and operation of the database. This fully applies to the inclusion dependencies, which are the theoretical basis for referential integrity on the data. Attempts to solve this problem contain inaccuracy in the statement of the problem and its solution. The errors in formulation of the problem can be associated with the use in the definition of untyped inclusion dependencies, which leads to permutations of the attributes, although, the attributes in database technology are identified by name and not by their place. In addition, linking with the use of the inclusion dependencies of heterogeneous attributes, even of the same type, is a sign of lost functional dependencies and leads to interaction of inclusion dependencies and non-trivial functional dependencies. Inaccuracies in the solution of the problem are contained in the statements of axioms and the proof of their properties, including completeness. In this paper we propose an original solution of this problem only for typed inclusion dependencies in the presence of Null values: a new axiom system is proposed, its completeness and soundness are proved. On the basis of inference rules we developed an algorithm for the construction of a not surplus set of typed inclusion dependencies. The correctness of the algorithm is proved.Неопределенные значения стали актуальной проблемой с момента создания реляционной модели данных. Влияние неопределенностей сказывается на всех видах зависимостей, используемых при проектировании и эксплуатации базы данных. В полной мере это относится и к зависимостям включения, которые являются теоретической основой ссылочной целостности на данные. Попытки решения указанной проблемы содержат неточности как в постановке задачи, так и в самом ее решении. К постановочным ошибкам можно отнести использование в определении нетипизированных зависимостей включения, что приводит к перестановкам атрибутов, хотя в технологиях баз данных атрибуты идентифицируются по имени, а не по их позиции. Кроме того, связывание зависимостью включения разнородных, пусть даже однотипных, атрибутов является признаком потерянной функциональной зависимости и приводит к взаимодействию нетривиальных зависимостей включения и функциональных зависимостей. Зависимости включения должны определять количественное соотнесение объектов друг с другом, а не значений атрибутов. Неточности в решении указанной проблемы содержатся в формулировках аксиом и доказательстве их свойств, в том числе полноты. В этой статье предлагается оригинальное решение этой проблемы только для типизированных зависимостей включения при наличии неопределенных значений: предложена система аксиом, доказана ее полнота и непротиворечивость. На основе правил вывода разработан алгоритм построения не избыточного множества типизированных зависимостей включения. Доказана корректность этого алгоритма
Задача о кратчайшем пути в кратном графе
Get PDFIn the article, the definition of an undirected multiple graph of any natural multiplicity k > 1 is stated. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is the union of k linked edges, which connect 2 or k+1 vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common ending vertex to k linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Also, a class of the divisible multiple graphs is considered. The main peculiarity of them is a possibility to divide the graph into k parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The following terms are generalized: the degree of a vertex, the connectedness of a graph, the path, the cycle, the weight of an edge, and the path length. There is stated the definition of the reachability set for the ordinary and multiple edges. The adjacency property is defined for a pair of reachability sets. It is shown, that we can check the connectedness of some multiple graph with the polynomial algorithm based on the search for the reachability sets and testing their adjacency. There is considered a criterion of the existence of a multiple path between two given vertices. The shortest multiple path problem is stated. Then we suggest an algorithm of finding the shortest path in a multiple graph. It uses Dijkstra’s algorithm of finding the shortest paths in subgraphs, which correspond to different reachability sets.В статье вводится определение неориентированного кратного графа произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или k + 1 вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна какому-либо кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер какого-либо мультиребра. Если вершина является общим концом какого-либо мультиребра, то она не может быть общим концом никакого другого мультиребра. Отдельно рассматривается класс делимых кратных графов, основной особенностью которых является возможность выделения k частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом. Для кратного графа обобщаются понятия степени вершины, связности графа, пути, цикла, веса ребра и длины пути. Вводится понятие множества достижимости по обычным и по кратным ребрам, определяется свойство смежности двух множеств достижимости. Показано, что проверка связности кратного графа может быть выполнена за полиномиальное время с помощью алгоритма, основанного на поиске множеств достижимости и проверки их смежности. Рассматривается критерий существования кратного пути между двумя вершинами и ставится задача о кратчайшем кратном пути. Строится алгоритм поиска кратчайшего пути в кратном графе, который использует алгоритм Дейкстры для поиска кратчайших путей в подграфах, соответствующих отдельным множествам достижимости.
Cингулярно возмущенная эллиптическая задача Дирихле с трехзонным пограничным слоем
Get PDFAbstract. A singularly perturbed elliptic problem with Dirichlet boundary conditions is considered in the case of multiple roots of the degenerate equation. A three-zone boundary layer arises in the vicinity of the domain boundary with a different scale of boundary-layer variables and a different behaviour of the solution in different zones. The asymptotic expansion of the solution being in fractional powers of the small parameter, boundary-layer series are constructed using a non-standard algorithm. A complete asymptotic expansion of the solution is constructed and justified.Исследована сингулярно возмущенная эллиптическая задача с граничными условиями Дирихле в случае кратного корня вырожденного уравнения. Возникает трехзонный пограничный слой с различным масштабом погранслойных переменных и различным характером поведения решения в разных зонах, асимптотическое разложение решения ведется по дробным степеням малого параметра. Построено и обосновано полное асимптотическое разложение решения задачи