Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

В этой статье я покажу вам 10 самых распространенных структур данных.

Перевод статьи Аллана О’Доннелла Learning C with GDB.

Исходя из особенностей таких высокоуровневых языков, как Ruby, Scheme или Haskell, изучение C может быть сложной задачей. В придачу к преодолению таких низкоуровневых особенностей C, как ручное управление памятью и указатели, вы еще должны обходиться без REPL. Как только Вы привыкнете к исследовательскому программированию в REPL, иметь дело с циклом написал-скомпилировал-запустил будет для Вас небольшим разочарованием.

Недавно мне пришло в голову, что я мог бы использовать GDB как псевдо-REPL для C. Я поэкспериментировал, используя GDB как инструмент для изучения языка, а не просто для отладки, и оказалось, что это очень весело.

Всем привет. На днях возникла идея написать статьи про основы компьютерных сетей, разобрать работу самых важных протоколов и как строятся сети простым языком. Заинтересовавшихся приглашаю под кат.

Дорогие мои друзья, отважные критики, тихие читатели и тайные почитатели, СДСМ заканчивается.



Я не могу похвастаться тем, что за 7 лет я затронул все темы сетевой сферы или тем, что хотя бы одну из них раскрыл полностью. Но это и не было целью. А целью этой серии статей было ввести юного студента за руку в этот мир и проводить его шаг за шагом по основной галерее, давая общее представление, и уберечь от болезненных скитаний по тёмным уголкам сознания Олифера и Олифера в мучительных попытках найти ответ на вопрос, как всё это применить в жизни.
СДСМ планировался коротким практическим курсом «как научиться в сети за месяц», а вылился в 16 (на самом деле 19) длинных выпусков, которые мы уже даже переименовали в «Сети Для Самых Суровых». Общее количество символов перевалило за 1 000 000.

Предисловие

В этой статье речь пойдет о методах решения задач математической оптимизации, основанных на использовании градиента функции. Основная цель — собрать в статье все наиболее важные идеи, которые так или иначе связаны с этим методом и его всевозможными модификациями.

Введение

Бывают ситуации, когда очень хочется использовать любимый редактор, но под рукой нету *nix операционных систем, либо разработка ведётся на Windows.

Первое что приходит на ум — использование Windows версии gVim, но в этом случае возникает куча проблем с установкой плагинов, переносом конфигов и адаптации всего и вся. Что-то не будет компилироваться без бубна (например Ctrl-p), а что-то падать во время работы.

Хочу поговорить об устройстве управления памятью (Memory Management Unit, MMU). Как вы, разумеется, знаете, основной функцией MMU является аппаратная поддержка виртуальной памяти. Словарь по кибернетике под редакцией академика Глушкова говорит нам, что виртуальная память — это воображаемая память, выделяемая операционной системой для размещения пользовательской программы, ее рабочих полей и информационных массивов.

У систем с виртуальной памятью четыре основных свойства:

1. Пользовательские процессы изолированы друг от друга и, умирая, не тянут за собой всю систему
2. Пользовательские процессы изолированы от физической памяти, то есть знать не знают, сколько у вас на самом деле оперативки и по каким адресам она находится.
3. Операционная система гораздо сложнее, чем в системах без виртуальной памяти
4. Никогда нельзя знать заранее, сколько времени займет выполнение следующей команды процессора

Выгода от всех вышеперечисленных пунктов очевидна: миллионы криворуких прикладных программистов, тысячи разработчиков операционных систем и несчетное число эмбеддеров благодарны виртуальной памяти за то, что все они до сих пор при деле.

К сожалению, по какой-то причине все вышеперечисленные товарищи недостаточно почтительно относятся к MMU, а их знакомство с виртуальной памятью обычно начинается и заканчивается изучением страничной организации памяти и буфера ассоциативной трансляции (Translation Lookaside Buffer, TLB). Самое интересное при этом остается за кадром.

Стиль описания конечного автомата как образ мышления

Когда нужно преодолеть врожденную параллельность FPGA, и появляется желание заставить схему работать последовательно, по алгоритму, на помощь приходят конечные автоматы, про которые написано не мало академических и практических трудов.

Например, очень популярной является работа: Clifford E. Cummings, The Fundamentals of Efficient Synthesizable Finite State Machine Design using NC-Verilog and BuildGates. Всякий раз, когда специалисты решают обсудить, как правильно писать конечные автоматы, кто-то обязательно достает эту публикацию.

Статья стала настолько авторитетной, что многие даже не стараются анализировать аргументы автора. В частности, бытует мнение, что профессионалы всегда используют двухчастный способ описания конечных автоматов, имеется ввиду, описание конечных автоматов в 2 always блока. Это утверждение продолжает вызывать жаркие споры, и я хочу пояснить различия в описаниях конечного автомата с разным количество always блоков.

В беседах с коллегами я понял, что споры о том, как надо писать конечные автоматы в 1 или 2, 3 always блока, связаны с разным представлением (осознанием) реализуемого алгоритма, разным типом мышления. Попробую показать это на примере.

Я полагаю, что эта статья не первая статья о FSM и Verilog в вашей жизни, поэтому я не буду объяснять ни что такое конечный автомат, ни как он описывается на Verilog, а перейду сразу к делу.

Вы хотите узнать, как получить работу по проектированию электроники космического корабля? Мне надавно пришло предложение поинтервьироваться на позицию FPGA designer для Blue Origin (см. выше). Лично мне такая позиция не нужна (у меня уже есть позиция ASIC designer-а в другой компании), но я отметил, что технические требования к претендентам в Blue Origin точно совпадают с содержанием семинара для школьников и младших студентов, который пройдет 15-17 сентября на выставке ChipEXPO в Сколково, с поддержкой от РОСНАНО. Хотя разумеется на семинаре мы коснемся технологий Verilog и FPGA только на самом начальном уровне: базовые концепции и простые, но уже интересные, примеры. Чтобы устроится после этого в Blue Origin, вам все-же потребуется несколько лет учебы и работы.

Из-за короновируса семинар будет удаленный, поэтому принять участие смогут не только школьники и студенты Москвы, но и всей России, Украины, Казахстана, Калифорнии и других стран и регионов. Физически проводить лекции и удаленно помогать участникам будут преподаватели и инженеры МИЭТ, ВШЭ МИЭМ, МФТИ, Черниговского Политеха, Самарского университета, IVA Technologies и fpga-systems.ru.

Для участия сначала, еще до семинара, нужно пройти три части теоретического курса от РОСНАНО, под общим названием «Как работают создатели умных наночипов»: «От транзистора до микросхемы», «Логическая сторона цифровой схемотехники», «Физическая сторона цифровой схемотехники». Этот курс необходим, чтобы вы понимали, что вы делаете, по время практического семинара. По получению сертификата окончания теоретического онлайн-курса, вы можете зайти в офис РОСНАНО в Москве и получить бесплатную плату для практического семинара (если они останутся, преимущество имеют школьники). С этой платой вы можете работать дома, до, во время и после семинара в Сколково.

Как получить плату, подготовится к семинару и что на нем будет:

Многие начинающие разработчики ПЛИС (и ASIC) не до конца понимают влияние временных ограничений (constraints – далее констрейнты) на результаты синтеза; то, каким образом констрейнты используются в статическом временном анализе. Большая часть литературы по этой тематике сводится к рассмотрению всевозможных видов констрейнтов, но ничего не говорит о внутренней “кухне” и используемых алгоритмах. Рассмотрению констрейнтов посвящен и недавний пост по данной тематике на ГТ (geektimes.ru/post/254932/ [1]). Между тем, констрейнты — лишь вершина айсберга. Их использование должно опираться на фундаментальные знания о статическом временном анализе, которые дают, к примеру, в американских университетах, но ничего не рассказывают у нас. Поэтому, собственно, поговорим о фундаменте.

Здравствуйте. Эта статья написана для самых-самых новичков в мире ПЛИС, которые пока что совсем не знают что такое STA (static timing analysis). В ней я попытаюсь максимально просто и наглядно рассказать что такое временны́е ограничения (timing constraints), накладываемые на проекты под ПЛИС.

Статья создана на основе собственного опыта попыток объяснить самому себе, студентам-практикантам и любопытным коллегам эту тему так, чтобы не погружаться в заумные академические дебри, а максимально просто и прозрачно, бытовым языком. Я учился работать с ПЛИС без учебы и подготовки по этой теме и знаю по своему опыту насколько трудно что-то понять не имея теоретического базиса в этой теме и в схемотехнике. Для опытного плисовода описанное — элементарно. Но для какого-нибудь студента четвертого курса статья будет полезной и поможет разобраться во всех этих слэках, сетапах и холдах.

Всем привет!

Часто ко мне обращаются люди с вопросами по задачам из области цифровой обработки сигналов (ЦОС). Я подробно рассказываю нюансы, подсказываю нужные источники информации. Но всем слушателям, как показало время, не хватает практических задач и примеров в процессе познания этой области. В связи с этим я решил написать краткий интерактивный курс по цифровой обработке сигналов и выложить его в открытый доступ.

Большая часть обучающего материала для наглядного и интерактивного представления реализована с использованием Jupyter Notebook. Предполагается, что читатель имеет базовые знания из области высшей математики, а также немного владеет языком программирования Python.

Удивительно, но никто не написал ничего про игрушку «TIS-100», которая недавно появилась в Steam (стоит всего 150 рублей, уже 460 положительных отзывов против 6 отрицательных).

Сразу оговорюсь, что к авторам игры я отношения не имею, а вот сама эта игра — отличный инструмент для всех программистов, которые хотят сразиться друг с другом в оптимизации кода на выдуманном хитром ассемблере.

Итак, о чем игра?

Меня всегда интересовала цифровая схемотехника, а в частности языки описания аппаратуры — HDL. У меня давно лежала в списке будущего чтения книга Дэвида М. Хэррис и Сары Л. Хэррис «Цифровая схемотехника и архитектура компьютера», воспользовавшись свободным временем на самоизоляции, я добрался до этой замечательной книги. В процессе чтения я столкнулся с некоторыми трудностями, а в частности, как именно писать и отлаживать код в Quartus Prime. В процессе поисков мне очень помог сайт marsohod.org, но вот процесс симуляции схемы на этом сайте описан с использованием встроенных средств Quartus и в современных версиях программы, этих встроенных средств нет и необходимо использовать ModelSim. Чтобы как-то систематизировать те знания, которые я получил, используя Quartus и ModelSim, я решил написать эту статью. В процессе этой статьи я в качестве примера разберу задачу из книги Дэвида М. Хэррис и Сары Л. Хэррис «Цифровая схемотехника и архитектура компьютера», а конкретно задачу 3.26 про автомат газированной воды. На протяжении статьи я покажу, как установить Quartus, создать проект, написать код и произвести его симуляцию. Всем кому это будет интересно, добро пожаловать под кат.

"The joy of coding Python should be in seeing short, concise, readable classes that express a lot of action in a small amount of clear code — not in reams of trivial code that bores the reader to death."
Guido van Rossum

Python — язык программирования, на котором приятно писать и который приятно читать. Мы предлагаем тринадцать лекций осеннего курса CS центра, чтобы посмотреть вглубь языка и попробовать понять, как пользоваться всеми его возможностями. Лекции читает Сергей Лебедев, разработчик в компании JetBrains и преподаватель в Computer Science Center.

Мало освоить синтаксис, чтобы узнать язык программирования: нужно осознать идиомы языка и научиться их применять. В течение курса Сергей знакомит слушателей с идиомами и возможностями языка Python.

_{Фотография сделана осенью 2014 года в Страсбурге, за две недели до начала первого прочтения этого курса.}

В этой статье я постараюсь максимально доходчиво рассказать о таком простом, но эффективном методе оптимизации, как имитация отжига (simulated annealing). А чтобы не быть причисленным к далёким от практики любителям теоретизировать, я покажу как применить этот метод для решения задачи коммивояжёра.

Для понимания статьи Вам понадобятся минимальные навыки программирования и владение математикой на уровне 9 класса средней школы. Статья рассчитана на людей не знакомых с методами оптимизации или только делающих первые шаги в этом направлении.

Новый лабник «Цифровой синтез» продолжает традиции учебника Дэвида Харриса и Сары Харрис «Цифровая схемотехника и архитектура компьютера», скачивания которого завалили британский сайт. Лабник позволяет потрогать руками всю теорию из Харрис & Харрис на плате FPGA, от мигания лампочек до процессора. В лабнике также разобрана концепция конвейерной обработки, без которой вы не пройдете интервью на работу проектировщиком ни в одну микроэлектронную компанию. В конце показан путь от FPGA до ASIC, массовых микросхем, которые стоят в айфонах, теслах и ИИ-акселераторах.

В книжке есть интервью команды из Питера, которую Intel привез в свою штаб-квартиру в Silicon Valley за их победу на конкурсе Innovate FPGA. Книжку «Цифровой синтез: практический курс» поддержала ведущая компания в автоматизации пректирования микросхем Cadence Design Systems (на фото выше сибирячка Наташа стоит с FPGA платой перед штаб-квартирой Cadence в Silicon Valley — в посте будет ее видео).

Лабник делался под эгидой Высшей Школы Экономики / МИЭМ (Александр Романов, Вероника Прохорова и Игорь Агамирзян), при этом разные главы в нем писали преподаватели Московского, Киевского и Самарского университетов, Питерского ИТМО, Черниговского политеха и Университета Калифорнии Санта-Круз (Чарльз Данчек, вечернее отделение в Silicon Valley). В создании учебника приняли участие инженеры российских компании IVA Technologies (Станислав Жельнио, аппаратный ускоритель ИИ + образовательный проект schoolMIPS) и ФГУП НПЦАП
(отделение Роскосмоса), американских компаний MIPS, Juniper Networks и AMD. Издало учебник ДМК-Пресс.

Внутри многокристального секционного микропроцессора Am2901 от AMD 1970-х годов

Вы, возможно, знакомы с современными процессорами производства компании Advanced Micro Devices. Но AMD начала производить процессоры ещё в 1975 году, когда впервые представила свой Am2901. Это был т.н. многокристальный секционный процессор: каждый из чипов обрабатывал по 4 бита, а для увеличения размера слова использовалась работа нескольких чипов одновременно. Такой подход использовали в 1970-х и 1980-х годах, чтобы создавать процессоры на 16, 32 или 64 бит (к примеру), когда не могли разместить целый процессор на одном быстром чипе. Существовали процессоры и на одном чипе, однако их МОП-транзисторы работали медленнее. Со временем процессоры на КМОП стали быстрее процессоров на биполярных транзисторах, и когда их скорость достаточно выросла, на них перешли почти все производители.


Фото кристалла с чипом Am2901. Видны металлические слои чипа; кремний находится внизу. По краям кристалла крохотные проводники соединяют чип с внешними контактами.

Типичная новость про электронику начала 2020 года: «Intel, вероятно, не будет размещать заказ на производство у TSMC, но рассматривает возможность сотрудничества с GlobalFoundries». Кто такие Intel — всем понятно, но что за GlobalFoundries и TSMC? Когда деревья были большими, каждая микроэлектронная компания самостоятельно производила свои микросхемы, а то и технику на их основе, как какая-нибудь Toshiba или IBM. С тех пор утекло много воды, производство подорожало, сложность приборов возросла, и в создании такого приземленного и распространенного девайса, как айфон, участвует несколько десятков высокотехнологичных компаний с трех континентов. Размеры мирового рынка полупроводниковых микросхем и приборов оцениваются больше, чем в 400 миллиардов долларов, но не все гиганты этого рынка имеют дело с конечными пользователями и часто появляются в новостях. Зато когда появляются — могут сбить с толку. Чтобы этого не происходило, я попробую кратко описать, кто есть кто.