API tools faq
paste
Advertisement
KDOXG

Hache (Hash + Cache)

KDOXG
May 27th, 2019
501
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 16.11 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!