Made available in DSpace on 2016-06-02T19:05:31Z (GMT). No. of bitstreams: 1 DissED.pdf: 797835 bytes, checksum: 2cb1cf03ad0e87b75038c325d0b2f91c (MD5) Previous issue date: 2004-02-26 / Universidade Federal de Sao Carlos / An integrated caching and prefetching mechanism for a parallel network file system has the potential to improve both the speed and performance of I/O operations. Different cache policies and algorithms can be used in the system. Different prefetching mechanisms can also be used in the system. The performance of the I/O operations can also be influenced by other techniques, such as the assynchronous write, cache consistency and cache space organization and distribution. This work presents the implementation of an integrated caching and prefetching architecture, intended to be used in distributed file systems. Also, this work elaborates an adaptive access pattern discovery algorithm to be used in prefetching mechanisms, denominated CPS, and two prefetching strategies, called prefetch-on-empty and limited aggressive. As the case studies, this work presents two multimedia servers a on-demand multimedia server, and a streaming media server. The influence of the proposed cache and prefetching mechanisms on tested applications is discussed. This work presents and discusses the functionality of integrated caching and prefetching mechanisms, benchmarking the implemented algorithms and overviewing the influence of chosen policies on the applications behavior. / Um mecanismo integrado de cache e prefetching para um sistema de arquivos paralelos em rede tem o potencial para aumentar a velocidade e o desempenho das operações de entrada e saída de dados. Vários tipos de cache, com políticas e algoritmos variados, podem ser empregados. Além disto, mecanismos distintos de prefetching de dados podem ser utilizados. Outras técnicas, como a escrita assíncrona, a manutenção da consistência do cache e a organização e distribuição do espaço no cache também podem influenciar no desempenho destas operações. Este trabalho apresenta a implementação de uma arquitetura integrada de mecanismos de cache e prefetching para sistemas de arquivos distribuídos. Além disto, este trabalho elabora um algoritmo adaptativo de determinação do padrão de acesso para ser utilizado em mecanismos de prefetching, CPS, e duas estratégias de prefetching, denominadas prefetch-on-empty e limited aggressive. Como estudos de caso, o trabalho apresenta dois servidores multimídia um servidor de arquivos multimídia on-demand, e um servidor de mídia contínua (streaming). A in- fluência dos mecanismos propostos nos aplicativos estudados é discutida. O trabalho apresenta e discute a funcionalidade dos mecanismos integrados de cache e prefetching, avaliando os algoritmos implementados e a influência da escolha das políticas adequadas no funcionamento de aplicações do usuário.

Made available in DSpace on 2016-06-02T19:05:14Z (GMT). No. of bitstreams: 1 DissCRFL.pdf: 648230 bytes, checksum: a343ed1fae316081651385f830f464fb (MD5) Previous issue date: 2003-05-30 / Financiadora de Estudos e Projetos / This work presents an architecture for the development of a Video on Demand (Vod) Server using a Parallel Distributed File System. In the development of this work several aspects related to the project of VoD Servers are considered, including: optimized storing and retrieval of videos using appropriate striping unit and request sizes, and the monitoring of disk and network operation for the performance evaluation of the proposed system. The characteristics of the MPEG standard used for video compression are also studied and considered in the video transfers. We also discuss aspects related to the implementation of prefetching mechanisms in the VoD Server. The concept of cluster computing is also considered for efficient data distribution aiming at appropriate response time for satisfying the Quality of Service (QoS) require by the VoD users. / Este trabalho apresenta uma arquitetura para o desenvolvimento de um Servidor de Vídeo Sob Demanda (VoD) utilizando um Sistema de Arquivos Paralelos Distribuídos. No desenvolvimento deste trabalho vários tópicos relacionados à construção de servidores de VoD são considerados, entre eles: armazenamento e recuperação otimizados dos vídeos através da determinação de tamanhos apropriados para a unidade de distribuição e requisições de leitura e a coleta de informações dos discos e da rede para avaliação de desempenho do sistema proposto. As características do padrão utilizado para compressão dos vídeos, o MPEG, são estudadas e consideradas. Também são apresentadas discussões de como devem ser implementados mecanismos de prefetching em servidores de VoD. O conceito de paralelismo em aglomerados de computadores é explorado para que a distribuição eficiente dos dados forneça um tempo de resposta adequado e condizente com as exigências de QoS impostas pelos usuários da aplicação de VoD.

Ordonnancement d’E/S Transversal pour les Systèmes de Fichiers Parallèles : desApplications aux DispositifsCette thèse porte sur l’utilisation de l’ordonnancement d’Entrées/Sorties (E/S) pour atténuer leseffets d’interférence et améliorer la performance d’E/S des systèmes de fichiers parallèles. Ilest commun pour les plates-formes de calcul haute performance (HPC) de fournir une infrastructurede stockage partagée pour les applications qui y sont hébergées. Dans cette situation,où plusieurs applications accèdent simultanément au système de fichiers parallèle partagé, leursaccès vont souffrir de l’interférence, ce qui compromet l’efficacité des stratégies d’optimisationd’E/S.Nous avons évalué la performance de cinq algorithmes d’ordonnancement dans les serveurs dedonnées d’un système de fichiers parallèle. Ces tests ont été exécutés sur différentes platesformeset sous différents modèles d’accès. Les résultats indiquent que la performance des ordonnanceursest affectée par les modèles d’accès des applications, car il est important pouraméliorer la performance obtenue grâce à un algorithme d’ordonnancement de surpasser sessurcoûts. En même temps, les résultats des ordonnanceurs sont affectés par les caractéristiquesdu système d’E/S sous-jacent - en particulier par des dispositifs de stockage. Différents dispositifsprésentent des niveaux de sensibilité à la séquentialité et la taille des accès distincts, ce quipeut influencer sur le niveau d’amélioration de obtenue grâce à l’ordonnancement d’E/S.Pour ces raisons, l’objectif principal de cette thèse est de proposer un modèle d’ordonnancementd’E/S avec une double adaptabilité : aux applications et aux dispositifs. Nous avons extraitdes informations sur les modèles d’accès des applications en utilisant des fichiers de trace,obtenus à partir de leurs exécutions précédentes. Ensuite, nous avons utilisé de l’apprentissageautomatique pour construire un classificateur capable d’identifier la spatialité et la taille desaccès à partir du flux de demandes antérieures. En outre, nous avons proposé une approche pourobtenir efficacement le ratio de débit séquentiel et aléatoire pour les dispositifs de stockage enexécutant des benchmarks pour un sous-ensemble des paramètres et en estimant les restantsavec des régressions linéaires.Nous avons utilisé les informations sur les caractéristiques des applications et des dispositifsde stockage pour décider automatiquement l’algorithme d’ordonnancement le plus appropriéen utilisant des arbres de décision. Notre approche améliore les performances jusqu’à 75% parrapport à une approche qui utilise le même algorithme d’ordonnancement dans toutes les situations,sans capacité d’adaptation. De plus, notre approche améliore la performance dans 64%de scénarios en plus, et diminue les performances dans 89% moins de situations. Nos résultatsmontrent que les deux aspects - des applications et des dispositifs - sont essentiels pour faire desbons choix d’ordonnancement. En outre, malgré le fait qu’il n’y a pas d’algorithme d’ordonnancementqui fournit des gains de performance pour toutes les situations, nous montrons queavec la double adaptabilité il est possible d’appliquer des techniques d’ordonnancement d’E/Spour améliorer la performance, tout en évitant les situations où cela conduirait à une diminutionde performance. / This thesis focuses on I/O scheduling as a tool to improve I/O performance on parallel file systemsby alleviating interference effects. It is usual for High Performance Computing (HPC)systems to provide a shared storage infrastructure for applications. In this situation, when multipleapplications are concurrently accessing the shared parallel file system, their accesses willaffect each other, compromising I/O optimization techniques’ efficacy.We have conducted an extensive performance evaluation of five scheduling algorithms at aparallel file system’s data servers. Experiments were executed on different platforms and underdifferent access patterns. Results indicate that schedulers’ results are affected by applications’access patterns, since it is important for the performance improvement obtained througha scheduling algorithm to surpass its overhead. At the same time, schedulers’ results are affectedby the underlying I/O system characteristics - especially by storage devices. Differentdevices present different levels of sensitivity to accesses’ sequentiality and size, impacting onhow much performance is improved through I/O scheduling.For these reasons, this thesis main objective is to provide I/O scheduling with double adaptivity:to applications and devices. We obtain information about applications’ access patternsthrough trace files, obtained from previous executions. We have applied machine learning tobuild a classifier capable of identifying access patterns’ spatiality and requests size aspects fromstreams of previous requests. Furthermore, we proposed an approach to efficiently obtain thesequential to random throughput ratio metric for storage devices by running benchmarks for asubset of the parameters and estimating the remaining through linear regressions.We use this information on applications’ and storage devices’ characteristics to decide the bestfit in scheduling algorithm though a decision tree. Our approach improves performance byup to 75% over an approach that uses the same scheduling algorithm to all situations, withoutadaptability. Moreover, our approach improves performance for up to 64% more situations, anddecreases performance for up to 89% less situations. Our results evidence that both aspects- applications and storage devices - are essential for making good scheduling choices. Moreover,despite the fact that there is no scheduling algorithm able to provide performance gainsfor all situations, we show that through double adaptivity it is possible to apply I/O schedulingtechniques to improve performance, avoiding situations where it would lead to performanceimpairment. / Esta tese se concentra no escalonamento de operações de entrada e saída (E/S) como uma soluçãopara melhorar o desempenho de sistemas de arquivos paralelos, aleviando os efeitos dainterferência. É usual que sistemas de computação de alto desempenho (HPC) ofereçam umainfraestrutura compartilhada de armazenamento para as aplicações. Nessa situação, em quemúltiplas aplicações acessam o sistema de arquivos compartilhado de forma concorrente, osacessos das aplicações causarão interferência uns nos outros, comprometendo a eficácia de técnicaspara otimização de E/S.Uma avaliação extensiva de desempenho foi conduzida, abordando cinco algoritmos de escalonamentotrabalhando nos servidores de dados de um sistema de arquivos paralelo. Foramexecutados experimentos em diferentes plataformas e sob diferentes padrões de acesso. Osresultados indicam que os resultados obtidos pelos escalonadores são afetados pelo padrão deacesso das aplicações, já que é importante que o ganho de desempenho provido por um algoritmode escalonamento ultrapasse o seu sobrecusto. Ao mesmo tempo, os resultados doescalonamento são afetados pelas características do subsistema local de E/S - especialmentepelos dispositivos de armazenamento. Dispositivos diferentes apresentam variados níveis desensibilidade à sequencialidade dos acessos e ao seu tamanho, afetando o quanto técnicas deescalonamento de E/S são capazes de aumentar o desempenho.Por esses motivos, o principal objetivo desta tese é prover escalonamento de E/S com duplaadaptabilidade: às aplicações e aos dispositivos. Informações sobre o padrão de acesso dasaplicações são obtidas através de arquivos de rastro, vindos de execuções anteriores. Aprendizadode máquina foi aplicado para construir um classificador capaz de identificar os aspectosespacialidade e tamanho de requisição dos padrões de acesso através de fluxos de requisiçõesanteriores. Além disso, foi proposta uma técnica para obter eficientemente a razão entre acessossequenciais e aleatórios para dispositivos de armazenamento, executando testes para apenas umsubconjunto dos parâmetros e estimando os demais através de regressões lineares.Essas informações sobre características de aplicações e dispositivos de armazenamento são usadaspara decidir a melhor escolha em algoritmo de escalonamento através de uma árvore dedecisão. A abordagem proposta aumenta o desempenho em até 75% sobre uma abordagem queusa o mesmo algoritmo para todas as situações, sem adaptabilidade. Além disso, essa técnicamelhora o desempenho para até 64% mais situações, e causa perdas de desempenho em até 89%menos situações. Os resultados obtidos evidenciam que ambos aspectos - aplicações e dispositivosde armazenamento - são essenciais para boas decisões de escalonamento. Adicionalmente,apesar do fato de não haver algoritmo de escalonamento capaz de prover ganhos de desempenhopara todas as situações, esse trabalho mostra que através da dupla adaptabilidade é possívelaplicar técnicas de escalonamento de E/S para melhorar o desempenho, evitando situações emque essas técnicas prejudicariam o desempenho.

Ordonnancement d’E/S Transversal pour les Systèmes de Fichiers Parallèles : desApplications aux DispositifsCette thèse porte sur l’utilisation de l’ordonnancement d’Entrées/Sorties (E/S) pour atténuer leseffets d’interférence et améliorer la performance d’E/S des systèmes de fichiers parallèles. Ilest commun pour les plates-formes de calcul haute performance (HPC) de fournir une infrastructurede stockage partagée pour les applications qui y sont hébergées. Dans cette situation,où plusieurs applications accèdent simultanément au système de fichiers parallèle partagé, leursaccès vont souffrir de l’interférence, ce qui compromet l’efficacité des stratégies d’optimisationd’E/S.Nous avons évalué la performance de cinq algorithmes d’ordonnancement dans les serveurs dedonnées d’un système de fichiers parallèle. Ces tests ont été exécutés sur différentes platesformeset sous différents modèles d’accès. Les résultats indiquent que la performance des ordonnanceursest affectée par les modèles d’accès des applications, car il est important pouraméliorer la performance obtenue grâce à un algorithme d’ordonnancement de surpasser sessurcoûts. En même temps, les résultats des ordonnanceurs sont affectés par les caractéristiquesdu système d’E/S sous-jacent - en particulier par des dispositifs de stockage. Différents dispositifsprésentent des niveaux de sensibilité à la séquentialité et la taille des accès distincts, ce quipeut influencer sur le niveau d’amélioration de obtenue grâce à l’ordonnancement d’E/S.Pour ces raisons, l’objectif principal de cette thèse est de proposer un modèle d’ordonnancementd’E/S avec une double adaptabilité : aux applications et aux dispositifs. Nous avons extraitdes informations sur les modèles d’accès des applications en utilisant des fichiers de trace,obtenus à partir de leurs exécutions précédentes. Ensuite, nous avons utilisé de l’apprentissageautomatique pour construire un classificateur capable d’identifier la spatialité et la taille desaccès à partir du flux de demandes antérieures. En outre, nous avons proposé une approche pourobtenir efficacement le ratio de débit séquentiel et aléatoire pour les dispositifs de stockage enexécutant des benchmarks pour un sous-ensemble des paramètres et en estimant les restantsavec des régressions linéaires.Nous avons utilisé les informations sur les caractéristiques des applications et des dispositifsde stockage pour décider automatiquement l’algorithme d’ordonnancement le plus appropriéen utilisant des arbres de décision. Notre approche améliore les performances jusqu’à 75% parrapport à une approche qui utilise le même algorithme d’ordonnancement dans toutes les situations,sans capacité d’adaptation. De plus, notre approche améliore la performance dans 64%de scénarios en plus, et diminue les performances dans 89% moins de situations. Nos résultatsmontrent que les deux aspects - des applications et des dispositifs - sont essentiels pour faire desbons choix d’ordonnancement. En outre, malgré le fait qu’il n’y a pas d’algorithme d’ordonnancementqui fournit des gains de performance pour toutes les situations, nous montrons queavec la double adaptabilité il est possible d’appliquer des techniques d’ordonnancement d’E/Spour améliorer la performance, tout en évitant les situations où cela conduirait à une diminutionde performance. / This thesis focuses on I/O scheduling as a tool to improve I/O performance on parallel file systemsby alleviating interference effects. It is usual for High Performance Computing (HPC)systems to provide a shared storage infrastructure for applications. In this situation, when multipleapplications are concurrently accessing the shared parallel file system, their accesses willaffect each other, compromising I/O optimization techniques’ efficacy.We have conducted an extensive performance evaluation of five scheduling algorithms at aparallel file system’s data servers. Experiments were executed on different platforms and underdifferent access patterns. Results indicate that schedulers’ results are affected by applications’access patterns, since it is important for the performance improvement obtained througha scheduling algorithm to surpass its overhead. At the same time, schedulers’ results are affectedby the underlying I/O system characteristics - especially by storage devices. Differentdevices present different levels of sensitivity to accesses’ sequentiality and size, impacting onhow much performance is improved through I/O scheduling.For these reasons, this thesis main objective is to provide I/O scheduling with double adaptivity:to applications and devices. We obtain information about applications’ access patternsthrough trace files, obtained from previous executions. We have applied machine learning tobuild a classifier capable of identifying access patterns’ spatiality and requests size aspects fromstreams of previous requests. Furthermore, we proposed an approach to efficiently obtain thesequential to random throughput ratio metric for storage devices by running benchmarks for asubset of the parameters and estimating the remaining through linear regressions.We use this information on applications’ and storage devices’ characteristics to decide the bestfit in scheduling algorithm though a decision tree. Our approach improves performance byup to 75% over an approach that uses the same scheduling algorithm to all situations, withoutadaptability. Moreover, our approach improves performance for up to 64% more situations, anddecreases performance for up to 89% less situations. Our results evidence that both aspects- applications and storage devices - are essential for making good scheduling choices. Moreover,despite the fact that there is no scheduling algorithm able to provide performance gainsfor all situations, we show that through double adaptivity it is possible to apply I/O schedulingtechniques to improve performance, avoiding situations where it would lead to performanceimpairment. / Esta tese se concentra no escalonamento de operações de entrada e saída (E/S) como uma soluçãopara melhorar o desempenho de sistemas de arquivos paralelos, aleviando os efeitos dainterferência. É usual que sistemas de computação de alto desempenho (HPC) ofereçam umainfraestrutura compartilhada de armazenamento para as aplicações. Nessa situação, em quemúltiplas aplicações acessam o sistema de arquivos compartilhado de forma concorrente, osacessos das aplicações causarão interferência uns nos outros, comprometendo a eficácia de técnicaspara otimização de E/S.Uma avaliação extensiva de desempenho foi conduzida, abordando cinco algoritmos de escalonamentotrabalhando nos servidores de dados de um sistema de arquivos paralelo. Foramexecutados experimentos em diferentes plataformas e sob diferentes padrões de acesso. Osresultados indicam que os resultados obtidos pelos escalonadores são afetados pelo padrão deacesso das aplicações, já que é importante que o ganho de desempenho provido por um algoritmode escalonamento ultrapasse o seu sobrecusto. Ao mesmo tempo, os resultados doescalonamento são afetados pelas características do subsistema local de E/S - especialmentepelos dispositivos de armazenamento. Dispositivos diferentes apresentam variados níveis desensibilidade à sequencialidade dos acessos e ao seu tamanho, afetando o quanto técnicas deescalonamento de E/S são capazes de aumentar o desempenho.Por esses motivos, o principal objetivo desta tese é prover escalonamento de E/S com duplaadaptabilidade: às aplicações e aos dispositivos. Informações sobre o padrão de acesso dasaplicações são obtidas através de arquivos de rastro, vindos de execuções anteriores. Aprendizadode máquina foi aplicado para construir um classificador capaz de identificar os aspectosespacialidade e tamanho de requisição dos padrões de acesso através de fluxos de requisiçõesanteriores. Além disso, foi proposta uma técnica para obter eficientemente a razão entre acessossequenciais e aleatórios para dispositivos de armazenamento, executando testes para apenas umsubconjunto dos parâmetros e estimando os demais através de regressões lineares.Essas informações sobre características de aplicações e dispositivos de armazenamento são usadaspara decidir a melhor escolha em algoritmo de escalonamento através de uma árvore dedecisão. A abordagem proposta aumenta o desempenho em até 75% sobre uma abordagem queusa o mesmo algoritmo para todas as situações, sem adaptabilidade. Além disso, essa técnicamelhora o desempenho para até 64% mais situações, e causa perdas de desempenho em até 89%menos situações. Os resultados obtidos evidenciam que ambos aspectos - aplicações e dispositivosde armazenamento - são essenciais para boas decisões de escalonamento. Adicionalmente,apesar do fato de não haver algoritmo de escalonamento capaz de prover ganhos de desempenhopara todas as situações, esse trabalho mostra que através da dupla adaptabilidade é possívelaplicar técnicas de escalonamento de E/S para melhorar o desempenho, evitando situações emque essas técnicas prejudicariam o desempenho.

Nos últimos anos, a evolução dos processadores e redes para computadores de baixo custo foi muito maior se comparada com o aumento do desempenho dos discos de armazenamento de dados. Com isso, muitas aplicações estão encontrando dificuldades em atingir o pleno uso dos processadores, pois estes têm de esperar até que os dados cheguem para serem utilizados. Uma forma popular para resolver esse tipo de empecílio é a adoção de sistemas de arquivos paralelos, que utilizam a velocidade da rede local, além dos recursos de cada máquina, para suprir a deficiência de desempenho no uso isolado de cada disco. Neste estudo, analisamos alguns sistemas de arquivos paralelos e distribuídos, detalhando aqueles mais interessantes e importantes. Por fim, mostramos que o uso de um sistema de arquivos paralelo pode ser mais eficiente e vantajoso que o uso de um sistema de arquivos usual, para apenas um cliente. / In the last years, the evolution of the data processing power and network transmission for low cost computers was much bigger if compared to the increase of the speed of getting the data stored in disks. Therefore, many applications are finding difficulties in reaching the full use of the processors, because they have to wait until the data arrive before using. A popular way to solve this problem is to use a parallel file system, which uses the local network speed to avoid the performance bottleneck found in an isolated disk. In this study, we analyze some parallel and distributed file systems, detailing the most interesting and important ones. Finally, we show the use of a parallel file system can be more efficient than the use of a usual local file system, for just one client.

Nos últimos anos, a evolução dos processadores e redes para computadores de baixo custo foi muito maior se comparada com o aumento do desempenho dos discos de armazenamento de dados. Com isso, muitas aplicações estão encontrando dificuldades em atingir o pleno uso dos processadores, pois estes têm de esperar até que os dados cheguem para serem utilizados. Uma forma popular para resolver esse tipo de empecílio é a adoção de sistemas de arquivos paralelos, que utilizam a velocidade da rede local, além dos recursos de cada máquina, para suprir a deficiência de desempenho no uso isolado de cada disco. Neste estudo, analisamos alguns sistemas de arquivos paralelos e distribuídos, detalhando aqueles mais interessantes e importantes. Por fim, mostramos que o uso de um sistema de arquivos paralelo pode ser mais eficiente e vantajoso que o uso de um sistema de arquivos usual, para apenas um cliente. / In the last years, the evolution of the data processing power and network transmission for low cost computers was much bigger if compared to the increase of the speed of getting the data stored in disks. Therefore, many applications are finding difficulties in reaching the full use of the processors, because they have to wait until the data arrive before using. A popular way to solve this problem is to use a parallel file system, which uses the local network speed to avoid the performance bottleneck found in an isolated disk. In this study, we analyze some parallel and distributed file systems, detailing the most interesting and important ones. Finally, we show the use of a parallel file system can be more efficient than the use of a usual local file system, for just one client.