Как разделить тест grep на параллельное задание

Question

Я хочу написать программу, аналогичную команде grep, для работы с моим sql-файлом. Я надеюсь, что он может использовать все мои ядра, когда он работает. Используя MPI или просто Pthreads, это не имеет значения. Но, Как я могу разделить файл на 4 файла? Я имею в виду, если у меня есть текстовый файл размером 700 Мб, как заставить каждый поток обрабатывать 1/4 этого файла.

По моему мнению, мне нужно знать, сколько строк этого файла, затем установить различное смещение файла для потока. Это хороший способ, и как получить общее количество строк?

может быть, узнать, сколько строк в файле займет много времени:

madper@myhost ~ % time wc -l lineitem.tbl
6001215 lineitem.tbl
wc -l lineitem.tbl  0.20s user 0.40s system 4% cpu 12.996 total

Answer 1

Прежде всего, ваша статистика во время выполнения выглядит так, как будто программа ограничена вводом / выводом.Существует огромное количество запасных процессоров.Таким образом, параллельное выполнение части процессора вряд ли будет иметь большое положительное значение.На самом деле, это может ухудшить ситуацию, поскольку кэширование на диске может быть менее эффективным.

Был длинный цикл работ по решению аналогичной проблемы Тимом Бреем в http://www.tbray.org/ongoing/When/200x/2007/09/20/Wide-Finder

.Многие люди занимаются исследованием подобного рода проблем (сканирование системных журналов), поэтому вы можете найти там готовую помощь.

Answer 2

То, что вы хотите сделать, не очень легко. Фреймворки, такие как Google MapReduce и Apache Hadoop, были созданы для решения подобных проблем. В общем случае разделение произвольного большого файла для произвольной параллельной обработки является сложной проблемой, и для этой задачи лучше всего использовать специальную инфраструктуру. Но в вашем случае, поскольку у вас, похоже, очень специфические требования, вы можете сделать что-то вроде:

Разделить файл на N кусков (где N = количество ядер). Очевидно, что это не будет учитывать границы строк, поэтому вам понадобится подпрограмма «splitter», которая ищет следующий символ новой строки в каждом чанке. (Это может быть сложно сделать правильно и избежать дублирования, но это в основном то, что делает Hadoop или MapReduce.) Затем вы можете обрабатывать каждый блок параллельно.

Конечно, это может быть неэффективно, как вы думаете. Если весь файл не помещается в памяти, вы столкнетесь с проблемами ввода-вывода. То, что вы распараллеливаете использование процессора, не обязательно означает, что вы распараллеливаете ввод-вывод. Вот почему платформы распределенной обработки обычно также распределяют данные по нескольким жестким дискам или узлам кластера.