Advertisement
KDOXG

Hache (Hash + Cache)

May 27th, 2019
502
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 16.11 KB | None | 0 0
  1. #include "lib_cache.c"
  2.  
  3. void hache()
  4. {
  5.     //Variaveis globais
  6.     int hits = 0, accesses = 0;
  7.     struct Miss misses;
  8.     misses.compulsory = 0;
  9.     misses.capacity = 0;
  10.     misses.conflict = 0;
  11.     float miss_rate;
  12.     struct Hache *hache;
  13.     int nsets = 256, bsize = 4, limit = 16;
  14.     char collision = '\0', *input_init;
  15.     FILE *input;
  16.  
  17.     /**--------------------- Inicialização
  18.      * O programa deverá receber como entrada uma string no seguinte formato:
  19.      *
  20.      * <tratamento_de_colisoes> <nsets_L1>:<bsize_L1>:<limit_L1> arquivo_de_entrada
  21.      *
  22.      * Legenda:
  23.      * <nsets_L1>: quantidade de conjuntos para armazenar na hache. Este número será dobrado toda vez que ou a hache lotar ou uma das listas encadeadas do Endereçamento Fechado atingir o limite. Valor padrão: 256
  24.      * <bsize_L1>: tamanho do bloco em bytes de cada endereço da hache. Valor padrão: 4
  25.      * <limit_L1>: Define a quantidade limite para uma lista encadeada no Endereçamento Fechado. Valor padrão: 16
  26.      * Caso os parâmetros inseridos não sejam números ou estejam vazios, o programa usará os valores padrões definidos anteriormente.
  27.      *
  28.      * <tratamento_de_colisoes>: escolher o algoritmo para tratar colisões de dados.
  29.      * Os macros suportados para configurar esta opção são:
  30.      * "chaining" - Endereçamento Fechado: insere o elemento no próximo ponteiro vazio disponível na posição retornada pela função hash
  31.      * "overflow" - Endereçamento Aberto Linear: insere o elemento no próximo espaço vazio a seguir da posição retornada pela função hash
  32.      * "re-hash" - Endereçamento Aberto Duplo: insere o elemento no próximo espaço vazio que a função hash encontrar pela posição incrementada com o valor retornado pela função hash auxiliar
  33.      * Se a palavra inserida não pertencer a estes macros, qualquer parâmetro inserido será ignorado e o programa usará a opção "chaining". Este nome não pode ser vazio.
  34.      *
  35.      * arquivo_de_entrada: nome do arquivo de entrada que armazena todos os endereços divididos em 4 bytes para a simulação. Este nome não pode ser vazio.
  36.      *
  37.      * A saída será os valores passados pela string formatados para suas respectivas variáveis.
  38.     /*/
  39.  
  40.     /** Função:
  41.      * Detectar se a string passada para input_init poderá ser formatada corretamente.
  42.      * Se for possível, extrair da string os números necessários para configurar a hache
  43.      * e o nome do arquivo para simulação.
  44.      */
  45.     {
  46.         input_init = malloc(80*sizeof(char));
  47.         fgets(input_init, 80, stdin);
  48.  
  49.         short int i, count_1=0, count_2=0, Error=0;
  50.         for (i=0; input_init[i] != '\0'; i++)
  51.         {
  52.             if (input_init[i] == ' ' && i == 0)
  53.                 Error = 1;
  54.             if (input_init[i] == ' ')
  55.                 count_1++;
  56.             if (count_1 == 1 && input_init[i] == ':')
  57.                 count_2++;
  58.             if (count_1 == 2 && (input_init[i+1] == '\0' || input_init[i+1] == '\n'))
  59.                 Error = 1;
  60.             if (count_1 == 2 && input_init[i+1] != '\0' && input_init[i+1] != '\n' && input_init[i+1] != ' ')
  61.                 break;
  62.         }
  63.         if (Error != 0 || count_1 != 2 || count_2 != 2)
  64.         {
  65.             printf("Erro: parâmetros passados de forma incorreta! Retornando...");
  66.             free(input_init);
  67.             return;
  68.         }
  69.         else
  70.             printf("\n");
  71.  
  72.         char *collision_aux, *nsets_aux, *bsize_aux, *limit_aux, *input_file;
  73.         short int j=0, k=0;
  74.         collision_aux = input_init;
  75.         for (i=0; i<strlen(input_init); i++)
  76.         {
  77.             if (input_init[i] == ' ' && j == 0)
  78.             {
  79.                 input_init[i] = '\0';
  80.                 if (input_init[i+1] != ':')
  81.                     nsets_aux = input_init+i+1;
  82.                 else
  83.                     nsets_aux = NULL;
  84.  
  85.                 for (j=i+1; input_init[j] != ' '; j++)
  86.                 {
  87.                     if (input_init[j] == ':' && k == 0)
  88.                     {
  89.                         input_init[j] = '\0';
  90.                         if (input_init[j+1] != ':')
  91.                             bsize_aux = input_init+j+1;
  92.                         else
  93.                             bsize_aux = NULL;
  94.                         k=1;
  95.                     }
  96.                     if (input_init[j] == ':' && k == 1)
  97.                     {
  98.                         input_init[j] = '\0';
  99.                         if (input_init[j+1] != ' ')
  100.                             limit_aux = input_init+j+1;
  101.                         else
  102.                             limit_aux = NULL;
  103.                     }
  104.                 }
  105.                 input_init[j] = '\0';
  106.                 input_file = (input_init+j+1);
  107.                 for (k=0; input_init[k] != '\n'; k++);
  108.                 input_init[k] = '\0';
  109.                 break;
  110.             }
  111.         }
  112.  
  113.         if (strcmp(collision_aux,"chaining") == 0)
  114.             collision |= 0;
  115.         if (strcmp(collision_aux,"overflow") == 0)
  116.             collision |= 1;
  117.         if (strcmp(collision_aux,"re-hash") == 0)
  118.             collision |= 2;
  119.  
  120.         int parametro_1=atoi(nsets_aux), parametro_2=atoi(bsize_aux), parametro_3=atoi(limit_aux);
  121.         if (parametro_1 != 0)
  122.             nsets = parametro_1;
  123.         if (parametro_2 != 0)
  124.             bsize = parametro_2;
  125.         if (parametro_3 != 0)
  126.             limit = parametro_3;
  127.  
  128.         input = fopen(input_file,"rb");
  129.  
  130.         free(input_init);
  131.         if (input == NULL)
  132.         {
  133.             printf("Erro: não foi possível ler o arquivo! Retornando...");
  134.             return;
  135.         }
  136.     }
  137.  
  138.     hache = malloc(nsets*sizeof(struct Hache));
  139.     initializeHache(hache,nsets);
  140.  
  141.     /**--------------------- Execução
  142.      * O programa deverá receber uma série de valores de entrada, valores estes que serão os endereços procurados
  143.      * posteriormente na matriz criada pelo simulador na inicialização. Cada endereço será um número de 32 bits.
  144.      * A saída será a quantidade de hits e misses ocorridos.
  145.      */
  146.  
  147.     /** Função:
  148.      * Executará a simulação de buscas de endereços em uma hache de nível 1.
  149.      */
  150.     {
  151.         int tag, index,
  152.         b_offset = ceil(log2(bsize)),
  153.         file_count=0, hache_count=0, count,
  154.         i, id, id_chain;
  155.         Address address;
  156.         struct Hache *hache_aux, *chain_loop;
  157.  
  158.         while(fgetc(input) != EOF)
  159.         {
  160.             fseek(input,-1,SEEK_CUR);
  161.             fgets((char*)&address.a,5,input);
  162.             file_count += 4;
  163.             fseek(input,file_count,SEEK_SET);
  164.             tag = address.a >> b_offset;
  165.             index = hash(tag,nsets);
  166.  
  167.             if ((hache[index].valid << 7) >> 7 == 0)//bit de validade
  168.             {
  169.                 hache[index].valid |= 0b00000001;
  170.                 hache[index].tag = tag;
  171.                 hache_count++;
  172.                 misses.compulsory++;
  173.                 continue;
  174.             }
  175.  
  176.             if (hache[index].tag == tag)
  177.             {
  178.                 hits++;
  179.                 continue;
  180.             }
  181.  
  182.             if (collision >> 0 == 0)//chaining
  183.             {
  184.                 count = 0;
  185.                 chain_loop = hache[index].chain;
  186.                 while(chain_loop != NULL)
  187.                 {
  188.                     if (chain_loop->tag == tag)
  189.                     {
  190.                         hits++;
  191.                         break;
  192.                     }
  193.                     else
  194.                     {
  195.                         chain_loop = chain_loop->chain;
  196.                         count++;
  197.                     }  
  198.                 }
  199.  
  200.                 if (chain_loop == NULL)
  201.                 {
  202.                     if (count != limit)
  203.                     {
  204.                         chain_loop = &hache[index];
  205.                         while(chain_loop->chain != NULL)
  206.                             chain_loop = chain_loop->chain;
  207.                         chain_loop->chain = malloc(sizeof(struct Hache));
  208.                         chain_loop->chain->chain = NULL;
  209.                         chain_loop->chain->tag = tag;
  210.                         chain_loop->chain->valid |= 0b00000001;
  211.                         hache_count++;
  212.                         misses.conflict++;
  213.                         continue;
  214.                     }
  215.                     else
  216.                     {
  217.                         nsets *= 2;
  218.                         hache_aux = malloc(nsets*sizeof(struct Hache));
  219.                         initializeHache(hache_aux,nsets);
  220.                         for (i=0; i<(nsets/2); i++)
  221.                         {
  222.                             id = hash(hache[i].tag,nsets);
  223.                             addChaining(hache_aux,id,hache[i].tag);
  224.                             chain_loop = hache[i].chain;
  225.                             while(chain_loop != NULL)
  226.                             {
  227.                                 id_chain = hash(chain_loop->tag,nsets);
  228.                                 addChaining(hache_aux,id_chain,chain_loop->tag);
  229.                                 chain_loop = chain_loop->chain;
  230.                             }
  231.                         }
  232.                         deleteHache(hache,nsets/2);
  233.                         hache = hache_aux;
  234.  
  235.                         id = hash(tag,nsets);
  236.                         addChaining(hache,id,tag);
  237.                         misses.capacity++;
  238.                         hache_count++;
  239.                     }
  240.                 }
  241.                 continue;
  242.             }
  243.            
  244.             if (collision >> 1 == 0)//overflow
  245.             {
  246.                 for (id=index; id < nsets && (hache[id].valid << 7) >> 7 == 1; id++)
  247.                 {
  248.                     if (hache[id].tag == tag)
  249.                     {
  250.                         hits++;
  251.                         break;
  252.                     }
  253.                 }
  254.                 if (id < nsets && hache[id].tag != tag)
  255.                 {
  256.                     hache[id].tag = tag;
  257.                     hache[id].valid |= 0b00000001;
  258.                     misses.conflict++;
  259.                     hache_count++;
  260.                     continue;
  261.                 }
  262.                 if (id == nsets)
  263.                 {
  264.                     nsets *= 2;
  265.                     hache_aux = malloc(nsets*sizeof(struct Hache));
  266.                     initializeHache(hache_aux,nsets);
  267.                     for (i=0; i<(nsets/2); i++)
  268.                     {
  269.                         if ((hache[i].valid << 7) >> 7 == 1)
  270.                             id = hash(hache[i].tag,nsets);
  271.                         else
  272.                             continue;
  273.                         if ((hache_aux[id].valid << 7) >> 7 != 1)
  274.                         {
  275.                             hache[id].tag = hache[i].tag;
  276.                             hache[id].valid |= 0b00000001;
  277.                             continue;
  278.                         }
  279.                         while ((hache_aux[id].valid << 7) >> 7 == 1)
  280.                             id++;
  281.                         hache_aux[id].tag = hache[i].tag;
  282.                         hache_aux[id].valid |= 0b00000001;
  283.                     }
  284.                     free(hache);
  285.                     hache = hache_aux;
  286.  
  287.                     id = hash(tag,nsets);
  288.                     while ((hache[id].valid << 7) >> 7 == 1)
  289.                         id++;
  290.                     hache[id].tag = tag;
  291.                     hache[id].valid |= 0b00000001;
  292.                     misses.capacity++;
  293.                     hache_count++;
  294.                 }
  295.                 continue;
  296.             }
  297.  
  298.             if (collision >> 2 == 0)//re-hash
  299.             {
  300.                 id = index;
  301.                 count = 0;
  302.                 while (hache[id].tag != tag && (hache[id].valid << 7) >> 7 == 1 && count < nsets)
  303.                 {
  304.                     id = rehash(id,tag,nsets);
  305.                     count++;
  306.                 }
  307.                 if (hache[id].tag == tag)
  308.                 {
  309.                     hits++;
  310.                     continue;
  311.                 }
  312.                 if (count < nsets)
  313.                 {
  314.                     hache[id].tag = tag;
  315.                     hache[id].valid |= 0b00000001;
  316.                     misses.conflict++;
  317.                     hache_count++;
  318.                     continue;
  319.                 }
  320.                 else
  321.                 {
  322.                     nsets *= 2;
  323.                     hache_aux = malloc(nsets*sizeof(struct Hache));
  324.                     initializeHache(hache_aux,nsets);
  325.                     for (i=0; i<(nsets/2); i++)
  326.                     {
  327.                         if ((hache[i].valid << 7) >> 7 == 1)
  328.                             id = hash(hache[i].tag,nsets);
  329.                         else
  330.                             continue;
  331.                         if ((hache_aux[id].valid << 7) >> 7 != 1)
  332.                         {
  333.                             hache[id].tag = hache[i].tag;
  334.                             hache[id].valid |= 0b00000001;
  335.                             continue;
  336.                         }
  337.                         while ((hache_aux[id].valid << 7) >> 7 == 1)
  338.                             id = rehash(id,hache[i].tag,nsets);
  339.                         hache_aux[id].tag = hache[i].tag;
  340.                         hache_aux[id].valid |= 0b00000001;
  341.                     }
  342.                     free(hache);
  343.                     hache = hache_aux;
  344.  
  345.                     id = hash(tag,nsets);
  346.                     while ((hache[id].valid << 7) >> 7 == 1)
  347.                         id = rehash(id,tag,nsets);
  348.                     hache[id].tag = tag;
  349.                     hache[id].valid |= 0b00000001;
  350.                     misses.capacity++;
  351.                     hache_count++;
  352.                 }
  353.             }
  354.         }
  355.         accesses = misses.capacity + misses.compulsory + misses.conflict + hits;
  356.         miss_rate = 100 * (accesses-hits) / accesses;
  357.         deleteHache(hache,nsets);
  358.         fclose(input);
  359.     }
  360.  
  361.     /**--------------------- Finalização
  362.      * O programa exibirá um relatório sobre o acesso à memória.
  363.      */
  364.  
  365.     printf("########## SIMULADOR DE HACHE ##########\nDesenvolvido por: Senhor K (KDOXG)\nProjeto paralelo e pessoal\n(e também bônus secreto do meu 2º trabalho de AOC2)\n\n");
  366.  
  367.     printf("Objetivo da Hache:\nUma hache é uma tabela hash que contabiliza seus acessos de maneira similar a um simulador de memória cache (\"hash\" + \"cache\" = \"hache\")\nA hache contabiliza quantos acertos uma tabela hash construída com os parâmetros inseridos pelo usuario pode executar, e quantos erros ela pode cometer.\nOs erros são classificados em:\nConflito: quando um endereço é calculado para um novo dado mas tal endereço já está sendo ocupado por outro dado.\nUm novo endereço é recalculado de acordo com o tratamento de colisões escolhido.\nCapacidade: quando não há mais espaço disponível para novos dados.\nUma nova hache é alocada com o dobro do tamanho para suprir a quantidade.\nTais dados obtidos podem ser usados para fins estatísticos e análise de desempenho para uma tabela hash equivalente.\n\n");
  368.    
  369.     printf("Tamanho da hache: %d elementos\n", nsets);
  370.     printf("Tratamento de colisões: ");
  371.     if (collision >> 0 == 0)
  372.         printf("Endereçamento Fechado (Chaining) com limite %d\n", limit);
  373.     else if (collision >> 1 == 0)
  374.         printf("Endereçamento Aberto Linear (Overflow)\n");
  375.     else if (collision >> 1 == 0)
  376.         printf("Endereçamento Aberto Duplo (Re-hash)\n");
  377.  
  378.     printf("Função hash(Tag_Endereço,Tamanho): (Tag_Endereço + 1)² / Tamanho mod Tamanho\n");
  379.     printf("Função rehash(Tag_Endereço,Tamanho): (hash(Tag_Endereço,Tamanho) + (1 + Tag_Endereço mod (Tamanho - 1))) mod Tamanho\n");
  380.     printf("Quantidade de acessos: %d\n", accesses);
  381.     printf("Hits: %d\n", hits);
  382.     printf("Misses: %d\n", misses.capacity + misses.compulsory + misses.conflict);
  383.     printf("Misses compulsórios: %d\n", misses.compulsory);
  384.     printf("Misses de conflito: %d\n", misses.conflict);
  385.     printf("Misses de capacidade: %d\n", misses.capacity);
  386.     printf("Taxa de miss: %.2f%%", miss_rate);
  387.     printf("\nPrograma encerrado corretamente! Retornando...\n\n");
  388.    
  389.     return;
  390. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement