Directorio para informática y programación multinúcleo

Parte 1 Conocimientos básicos

1 Descripción general de la informática multinúcleo

1.1 Descripción general de la CPU multinúcleo

1.1.1 Multi La informática de múltiples núcleos se convertirá en una tendencia de desarrollo

1.1.2 Introducción a la arquitectura de hardware de CPU de múltiples núcleos

1.1.3 Oportunidades y desafíos que los múltiples núcleos brindan a los programadores

1.2 ¿Qué problemas encontrará la programación multinúcleo?

1.2.1 Problema de concurrencia

1.2.2 Problema de inanición de CPU

1.2.3 Descomposición de tareas y problema de programación

1.2.4 Problemas de rendimiento del índice de aceleración

1.2.5 Problemas de conservación de energía y protección del medio ambiente

1.2.6 Problemas de escalabilidad

1.3 La diferencia entre programación de múltiples núcleos y programación de múltiples subprocesos de un solo núcleo

1.3.1 La diferencia entre la serialización causada por la competencia de bloqueo

1.3.2 La diferencia entre la descomposición de subprocesos y ejecución

1.3.3 La diferencia entre el equilibrio de carga del núcleo de la CPU

1.3.4 Diferencias en las estrategias de programación de tareas

1.3.5 Diferencias en el acceso a CPUCache (pseudo * problema de compartir)

1.3.6 Prioridad de prioridad de tarea La diferencia

1.3.7 La diferencia entre computación en serie y computación paralela y distribuida

1.4 La diferencia entre programación multinúcleo y programación distribuida multimáquina

1.4 *** La diferencia entre almacenamiento compartido y almacenamiento distribuido

1.4.2 La diferencia entre informática distribuida

1.4.3 La diferencia en el entorno de programación

1.5 Coeficiente de relación de aceleración

1.5.1 Ley de Amdahl

1.5.2 Ley de Gustavson

1.5.3 Equivalencia de la ley de Amdahl y la ley de Gustafson

1.5.4Métrica de Karp-Flatt

1.5.5 Factores que afectan el coeficiente de aceleración en situaciones reales

1.5.6 Relación de aceleración en el caso de sobrecarga de computación paralela

1.6 Problemas de competencia de bloqueo y su impacto en la relación de aceleración

1.6.1 Factor de granularidad de subprocesos y factor de granularidad de bloqueo

1.6.2 Rendimiento de la competencia de bloqueos

p>

1.6.3 Análisis de aceleración en la competencia de bloqueos centralizados

1.6.4 Análisis de aceleración en la competencia de bloqueos aleatorios

1.6.5 Competencia de bloqueo distribuido Análisis de aceleración

1.6.6 Análisis de aceleración de la programación sin bloqueo

1.7 Impacto de los problemas de equilibrio de carga en la velocidad

1.7.1 Impacto en el equilibrio de carga Factores principales

1.7.2 Indicadores de evaluación del equilibrio de carga

1.7.3 Relación de aceleración bajo equilibrio de carga

1.8 Referencias

2 Conceptos básicos de la programación multiproceso

2.1 Conceptos básicos de la programación multiproceso

2.1.1 Hilos

2.1.2 Bloqueos

2.1.3 Operaciones de bloqueo y funciones de operación de semáforo comúnmente utilizadas en varios sistemas

2.1.4 Utilice C para realizar la liberación automática de bloqueos

2.1.5 Atómico operaciones

2.1.6 La diferencia entre bloqueos y operaciones atómicas

2.1.7 Los conceptos de computación con bloqueos, computación sin bloqueos y computación local

2.2 Rendimiento comparación de varias cerraduras

2.2.1 Rendimiento de varias cerraduras en situaciones de un solo subproceso

2.2.2 Rendimiento de varias cerraduras en situaciones de competencia de cerraduras centralizadas de múltiples subprocesos

2.2.3 Varios Rendimiento de los bloqueos en la competencia de bloqueos distribuidos de subprocesos múltiples

2.3 Algoritmo de bloqueo de lectura-escritura

2.3.1 Introducción al concepto de bloqueo de lectura-escritura

2.3.2 Análisis e implementación del algoritmo de bloqueo de lectura-escritura

2.3.3 Implementación de codificación del bloqueo de lectura-escritura

2.4 Algoritmo de salida multiproceso

2.4.1 Algoritmo de salida de subproceso único

2

.4.2 Salir cuando varios subprocesos acceden a recursos compartidos

2.4.3 Implementación de algoritmo de liberación y salida de recursos multiproceso con bloqueo

2.4.4 Algoritmo de salida sin bloqueo

2.4.5 Uso del algoritmo de salida multiproceso

2.5 Referencias

3Programación OpenMP

3.1Conceptos básicos de OpenMP

3.1.1 El concepto de modo de ejecución paralela fork/join

3.1.2 Modelo de memoria

3.1.3 Ejemplo de rendimiento

3.1.4 Compatibilidad con OpenMP del par de compiladores

3.2Modelo de programación OpenMP

3.2.1Formato de instrucción de instrucción de compilación OpenMP

3.2.2Comandos principales de OpenMP

3.2.3Cláusulas principales de OpenMP

3.2.4Funciones de la biblioteca principal de OpenMP

3.3 Creación de subprocesos y trabajo compartido

3.3.1comando paralelo

3.3.2comando for y paralelofor

3.3.3Cláusula if (paralelismo de ejecución condicional)

3.3.4 Establecer dinámicamente el número de subprocesos para bucles paralelos

3.3.5 Preguntas sobre paralelización de bucles

3.3.6 secciones y comandos de sección

3.3.7 comando único

3.3.8 comando maestro

3.4 Procesamiento de datos

3.4.1 cláusula privada

3.4.2 primera cláusula privada

3.4.3 última cláusula privada

3.4.4 cláusula privada de hilo

3.4.5 cláusula compartida

3.4.6 cláusula por defecto

3.4.7 cláusula de reducción

3.4.8 cláusula de copia

3.4.9 cláusula de copia privada

3.5 Programación de tareas

3.5.1 Uso de la cláusula de programación

3.5.2 Programación estática (estática)

3.5.3 Programación dinámica (dinámica)

3.5.4 Programación guiada (guiada)

3.5.5 Programación en tiempo de ejecución (rumtime)

3.5.6 Programación de tareas y pseudo ***problemas de uso compartido

3.6 Sincronización entre hilos

3.6.1comando de barrera

3.6.2comando crítico

3.6.3comando atómico

3.6.4comando ordenado y cláusula

3.6.5cláusula nowait

3.6.6comando de descarga

3.7Explicación detallada de la función de biblioteca OpenMP

p>

3.7. 1 Función de entorno de ejecución

3.7.2 Función de operación de bloqueo

3.7.3 Función de operación de tiempo

3.8Variable de entorno OpenMP

p>

3.8.1OMP_DYNAMIC

3.8.2OMP_NUM_THREADS

3.8.3OMP_NESTED

3.8.4OMP_SCHEDULE

3.9Variables de control interno de OpenMP y relacionados procesos

3.9.1 Variables de control interno

3.9.2 Proceso de programación de tareas

3.9.3 Proceso de decisión del número de subprocesos

3.10 Referencias

Parte 2 Algoritmos y estructuras de datos básicos

4 Números

Grupo

4.1 Pila

4.1.1 Concepto básico de pila

4.1.2 Implementación de codificación de pila

4.1.3 Multi- Threading Implementación de pila

4.2 Clasificación rápida de matrices

4.2.1 Introducción al algoritmo de clasificación

4.2.2 Idea básica de clasificación rápida en serie

4.2.3 Implementación de código de clasificación rápida en serie

4.2.4 Algoritmo de clasificación rápida no recursivo

4.2.5 Análisis de complejidad del algoritmo de clasificación rápida

4.3 Buscar en matriz

4.3.1 Búsqueda secuencial

4.3.2 Búsqueda binaria

4.4 Ejemplo: Usar matriz para gestionar una función HOOK

4.4.1 Implementación HOOK de una sola función

4.4.2 Implementación HOOK de múltiples funciones

4.4.3 Introducción a la aplicación de la función HOOK

4.4 .4 Precauciones al usar HOOK

4.5 Referencias

5 Lista enlazada

5.1 Lista enlazada unidireccional

5.1 .1 Representación de almacenamiento

5.1.2 Diseño de interfaz

5.1.3 Agregar nodo al encabezado de la lista vinculada

5.1.4 Codificación de funciones básicas implementación

5.2 Clasificación unidireccional de listas enlazadas

5.2.1 Ordenación por inserción

5.2.2 Ordenación por inserción fusionada

5.3 Doblemente listas enlazadas

5.3.1 Listas doblemente enlazadas Conceptos básicos

5.3.2 Diseño de listas doblemente enlazadas

5.3.3 Interfaz de operación de listas doblemente enlazadas

5.3.4 Implementación de codificación de listas doblemente enlazadas

5.4 Recorrido nodo por nodo de listas enlazadas

5.4.1 Conceptos básicos de recorrido nodo por nodo

5.4.2 Implementación de codificación transversal nodo por nodo

5.5 Algoritmo transversal de subprocesos múltiples

5.5.1 Implementación de diseño y codificación de listas enlazadas multiproceso

5.5.2 4 esquemas de recorrido de listas enlazadas de subprocesos múltiples

5.5.3 Múltiples La situación cuando los subprocesos atraviesan al mismo tiempo

5.6 Ejemplo: uso de enlaces listas para gestionar la caché de sistemas de mensajes cortos

5.6.1 Conceptos básicos de gestión de caché de sistemas de mensajes cortos

5.6.2 Análisis de envío y recepción de sistemas de mensajes cortos

5.6.3 Implementación de codificación de la gestión de caché del sistema de mensajes cortos

6 Tabla Hash

6.1 Tabla Hash

6.1.1 Conceptos básicos de hash tablas

6.1.2 Métodos de indexación de tablas hash

6.1.3 Métodos de resolución de conflictos de tablas hash

p>

6.1.4 Código fuente de operaciones básicas de la tabla hash

6.2 Lista enlazada hash

6.2.1 Comparación de eficiencia entre tabla hash, matriz y lista enlazada

6.2.2 La relación entre el tiempo eficiencia y eficiencia del espacio

6.2.3 Conceptos básicos de listas enlazadas hash

6.2.4 Operaciones de listas enlazadas hash

6.2.5 Implementación de codificación de listas enlazadas hash list

6.3 Ejemplo: Gestión dinámica de archivos CACHE de WebServer

6.3.1 Conceptos básicos de la gestión dinámica de archivos CACHE de WebServer

6.3.2 Diseño de archivos CACHE función de gestión

6.3.3 Implementación de codificación de la función de gestión de archivos CACHE

6.4 Referencias

7 Árboles ordinarios y árboles binarios

7.1 Ordinario árboles

7.1.1 Método de descripción de árboles ordinarios

7.1.2 Diseño de interfaz de operación de árbol

7.1.3 Algoritmo de recorrido de árbol

7.1.4 Implementación de codificación de árbol

7.1.5 Utilice el algoritmo transversal de árbol para implementar la función Xcopy

7

.2 Árbol binario

7.2.1 Conceptos básicos del árbol binario

7.2.2 La copa del árbol binario y la altura del árbol binario

7.2.3 El método de descripción del árbol binario

7.3 Árbol de clasificación binaria

7.3.1 Conceptos básicos del árbol de clasificación binaria

7.3.2 Búsqueda en binario árbol de clasificación

7.3.3 Inserción de árbol de clasificación binario

7.3.4 Eliminación de árbol de clasificación binario

7.3.5 Recorrido del árbol de clasificación binario

7.3 .6 Operación de rotación del árbol de clasificación binaria

8Árbol de búsqueda AVL

8.1Conceptos básicos del árbol de búsqueda AVL

8.2Inserción del árbol de búsqueda AVL

8.2.1 Cuestiones que deben considerarse en la operación de inserción

8.2.2 Análisis de la situación donde no hay nodos desequilibrados

8.2.3 Análisis de la situación del nodo A desequilibrado

8.2.4 Análisis de cuatro situaciones en las que existen nodos desequilibrados

8.2.5 Ajuste de la situación de desequilibrio del tipo LL

8.2 .6 Ajuste de la situación de desequilibrio del tipo LR

8.2.7 Descripción en pseudocódigo de la operación de inserción

8.3 Eliminación del árbol de búsqueda AVL

8.3.1 Determinación de Un nodo

8.3.2 Análisis de varias situaciones de desequilibrio

8.3.3 Análisis de ajuste de tipo L0

8.3.4 Análisis de ajuste de tipo L-1

8.3.5Análisis de ajuste de tipo L1

8.3.6 Descripción en pseudocódigo de la operación de eliminación

8.4 Árbol AVL con equilibrio de carga

8.4.1 Introducción de conceptos básicos

8.4.2 Ajuste del factor de carga en operación de inserción

8.4.3 Ajuste del factor de carga en operación de eliminación

8.4.4 L0 y L- 1 análisis de ajuste de tipo

8.4 Análisis de ajuste de tipo .5L1

Código fuente del árbol 8.5AVL

8.5.1 Definición de estructura de datos

8.5.2 Crear, liberar, buscar y otras operaciones

p>

8.5.3 Función de operación de rotación

8.5.4 Función de operación de inserción

8.5 .5 Función de operación de eliminación

8.6 Referencias

9 Árbol binario compuesto

9.1 Árbol hash rojo-negro

9.1.1 Concepto básico de Hash Red-Black Tree

9.1.1 Hash Búsqueda de árboles rojo-negro

9.1.3 Inserción de hash árboles rojo-negro

9.1.4 Eliminación de árboles hash rojo-negro

9.1.5 Ha Liberación de árbol hash rojo-negro

9.1.6 Recorrido del árbol hash rojo-negro

9.1 .7 Implementación de codificación del árbol hash rojo-negro

9.1.8 Análisis de eficiencia del árbol Hash Red-Black

9.2 Árbol Hash AVL

9.2.1 Básico Concepto de árbol Hash AVL

9.2.2 Hash buscando en el árbol AVL

9.2.3 Insertando el árbol hash AVL

9.2.4 Eliminando el árbol hash AVL

9.2.5 Lanzamiento del árbol Hash AVL

9.2.6 Recorrido del árbol hash AVL

9.2.7 Implementación de codificación del árbol hash AVL

9.3 Clasificación de estructuras de datos compuestos

p>

9.4 Ejemplos de ataques anti-DoS/DdoS

9.4.1 Concepto de ataques DoS/DdoS

9.4.2 Métodos comunes de ataques DoS/DdoS y estrategias de prevención

9.4.3 Implementación de ataques anti-DoS/DdoS

9.4.4 Implementación de codificación de anti-DoS/DdoS ataques

9.5 Referencias

Nº 3 Partes de la Computación Paralela

10 Patrones de Programación Paralela

10.1 Conceptos Básicos

>

10.1.1 Computación paralela fuerte y computación paralela débil

10.1.2 Ideas básicas de patrones de programación paralela

10.2 Patrón de descomposición de datos

10.3 Modo divide y vencerás

10.3.1 Problemas de equilibrio de carga al resolver subproblemas

10.3.2 Problemas de serialización que pueden deberse a la combinación de soluciones a subproblemas

10.4 Modo canalización

10.5 Modo paralelo de tareas

10.6 Modo de programación de tareas

10.6.1 Modo de programación de gráficos de tareas

10.6. 2 Modo de programación dinámica de tareas

11 Búsqueda paralela

11.1 Búsqueda secuencial paralela

11.1.1 Búsqueda paralela de datos específicos

11.1. 2 Número máximo de búsquedas paralelas

11.1.3 Algoritmo de detección de terminación

11.2 Búsqueda de ruta más corta de Dijkstra en serie

11.2.1 Descripción del algoritmo de ruta más corta de Dijkstra

11.2.2 Diagrama de proceso del algoritmo de ruta más corta de Dijkstra

11.2.3 Descripción del pseudocódigo

11.2.4 Diagrama de flujo del algoritmo

11.2.5C /Implementación de código C

11.3 Algoritmo de ruta más corta en paralelo

11.3.1 Paralelización del algoritmo de Dijkstra

11.3.2 Implementación de código del algoritmo de Dijkstra en paralelo

11.3.3 Introducción y análisis de otros algoritmos paralelos de ruta más corta

11.4 Referencias

12 Clasificación en paralelo

12.1 Descripción general de la clasificación en paralelo

12.2 Ordenación por burbujas

12.2.1 Ordenación por burbujas en serie

12.2.2 Ordenación por paridad

12.3 Ordenación rápida

12.3 . 1 Idea básica de clasificación rápida en serie

12.3.2 Implementación de código de clasificación rápida en serie

12.3.3 Método de paralelización de clasificación rápida

12.3.4 Ordenación rápida en paralelo en el proyecto de código abierto mcstl

12.3.5 Ordenación rápida basada en el robo de tareas

12.4 Ordenación por combinación en paralelo

12.4.1 Algoritmo de combinación en serie

12.4.2 Algoritmo de fusión paralela de Cole

12.4.3 Ordenación de fusión rápida paralela

12.5 Ordenación por base

12.5.1 Base de cadena en serie ordenar

12.5.2 Ordenar por base de matriz en serie

12.5.3 Ordenar jerárquico en un solo paso

12.5.4 Ordenar por base paralela con equilibrio de carga

12.5.5 Clasificación de particiones por bases paralelas

13 Cálculos numéricos paralelos

13.1 Problemas que enfrentan los cálculos numéricos paralelos de múltiples núcleos

13.1.1 Caché El Problema de tasa de aciertos

13.1.2 Problema de intercambio de pseudo***

13.2 Suma y suma de prefijos

13.3 Suma de matrices

13.4 Matriz multiplicación

13.4.1 Conceptos básicos

13.4.2 Algoritmo serial

13.4.3 Algoritmo paralelo

13.5 Multiplicación matriz-vector

13.6 Generación paralela de números aleatorios

13.7 Referencias

Parte 4 ***Computación distribuida de recursos compartidos

14 Patrones de diseño de computación distribuida

14.1 Conceptos básicos

14.1.1*** Descomposición computacional de recursos compartidos

14.1.2*** Compartir problemas de equilibrio de carga en la informática de recursos

14.1.3*** Ideas y métodos de diseño de algoritmos para la computación de recursos compartidos

14.2 Modo de competencia de agrupación de subprocesos<

/p>

14.2.1 Modo de competencia de agrupación de hilos estándar

14.2.2 Variaciones del modo de competencia de agrupación de hilos

14.3 Modo de competencia aleatoria de hilos

14.3 .1 Conceptos básicos

14.3.2 Garantía de rendimiento de la relación de aceleración

14.4 Modo de localización de datos

14.4.1 Lograr un rendimiento mejor que el de subprocesos múltiples de un solo núcleo

14.4.2 Modo de localización de datos

14.4.3 Análisis de ventajas y desventajas

14.5 Diseño de estructura de datos distribuidos

14.5 .1 Método de diseño de estructura de datos compuesta

14.5.2 Diseño de estructura de datos distribuidos

14.5.3 Principales cuestiones de la estructura de datos distribuidos

14.6 Referencias

p>

15 Cola distribuida

15.1 Cola serie

15.1.1 Cola de anillo simple

15.1.2 Deque en STL

15.1.3 Cola de timbre dinámico

15.2 Grupo de colas

15.2.1*** Cola compartida

15.2.2 Cola de mensajes

15.2.3 Grupo de colas

15.2.4 Varios esquemas de implementación del grupo de colas

15.2.5 Ejemplos de uso del grupo de colas

15.3 Con informática local distribuida cola

15.3.1 Idea básica

15.3.2 Implementación de cola localizada

15.3.3 Implementación de cola de robo de tareas

p >

15.3.4 Implementación de cola distribuida

15.3.5 Implementación del grupo de subprocesos CThreadPool

15.3.6 Implementación de código del grupo de subprocesos CThreadPool

15.3 .7Código fuente de CDistributedQueue

15.3.8Ejemplos de uso de CDistributedQueue

16 Búsqueda distribuida

16.1 Problemas e ideas principales de la búsqueda en multinúcleo

16.2 Diseño de estructura de búsqueda secundaria para equilibrio de carga estática

16.2.1 Diseño de estructura de búsqueda secundaria

16.2.2 Árbol AVL hash distribuido

16.2.3 Distribuido árbol AVL secuencial

16.3 Diseño de estructura de búsqueda multinivel para equilibrio de carga dinámico

16.3.1 Problemas de equilibrio de carga en la búsqueda distribuida

16.3.2 Multinivel Método de diseño de estructura de búsqueda

16.3.3 Algoritmo de búsqueda de tabla de búsqueda multinivel

16.3.4 Algoritmo de operación de inserción de tabla de búsqueda multinivel

16.3.5 Eliminar algoritmo de operación de la tabla de búsqueda multinivel

16.3.6 Tabla de secuencia multinivel

16.3.7 Árbol AVL de índice multinivel

16.3 .8 Distribuido árbol AVL multinivel hash

16.3.9 Árbol AVL secuencial distribuido multinivel

16.4 Método de selección del algoritmo de búsqueda en un entorno multinúcleo

16.5 Dinámico Ejemplo de diseño de WebCache

17 Gestión de memoria distribuida

17.1 Ideas básicas de gestión de memoria multinúcleo

17.1.1 Requisitos de gestión de memoria

17.1.2 Ideas de gestión de memoria en sistemas multinúcleo

17.2 Gestión de memoria de igual tamaño

17.2.1 Conceptos básicos de gestión de memoria Freelist

17.2.2 Implementación de codificación de listas libres

17.2.3 Gestión de memoria de FreeLists

17.3 Gestión de memoria en el proyecto de código abierto Intel TBB

17.3.1 Problema de intercambio de pseudo******

17.3.2 Gestión de memoria alineada con caché